| // Copyright 2012 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef V8_HEAP_MARK_COMPACT_H_ |
| #define V8_HEAP_MARK_COMPACT_H_ |
| |
| #include <atomic> |
| #include <vector> |
| |
| #include "src/heap/concurrent-marking.h" |
| #include "src/heap/marking.h" |
| #include "src/heap/objects-visiting.h" |
| #include "src/heap/spaces.h" |
| #include "src/heap/sweeper.h" |
| #include "src/heap/worklist.h" |
| #include "src/objects/heap-object.h" // For Worklist<HeapObject, ...> |
| #include "src/objects/js-weak-refs.h" // For Worklist<WeakCell, ...> |
| |
| namespace v8 { |
| namespace internal { |
| |
| // Forward declarations. |
| class EvacuationJobTraits; |
| class HeapObjectVisitor; |
| class ItemParallelJob; |
| class MigrationObserver; |
| class RecordMigratedSlotVisitor; |
| class UpdatingItem; |
| class YoungGenerationMarkingVisitor; |
| |
| template <typename ConcreteState, AccessMode access_mode> |
| class MarkingStateBase { |
| public: |
| V8_INLINE MarkBit MarkBitFrom(HeapObject obj) { |
| return MarkBitFrom(MemoryChunk::FromHeapObject(obj), obj.ptr()); |
| } |
| |
| // {addr} may be tagged or aligned. |
| V8_INLINE MarkBit MarkBitFrom(MemoryChunk* p, Address addr) { |
| return static_cast<ConcreteState*>(this)->bitmap(p)->MarkBitFromIndex( |
| p->AddressToMarkbitIndex(addr)); |
| } |
| |
| Marking::ObjectColor Color(HeapObject obj) { |
| return Marking::Color(MarkBitFrom(obj)); |
| } |
| |
| V8_INLINE bool IsImpossible(HeapObject obj) { |
| return Marking::IsImpossible<access_mode>(MarkBitFrom(obj)); |
| } |
| |
| V8_INLINE bool IsBlack(HeapObject obj) { |
| return Marking::IsBlack<access_mode>(MarkBitFrom(obj)); |
| } |
| |
| V8_INLINE bool IsWhite(HeapObject obj) { |
| return Marking::IsWhite<access_mode>(MarkBitFrom(obj)); |
| } |
| |
| V8_INLINE bool IsGrey(HeapObject obj) { |
| return Marking::IsGrey<access_mode>(MarkBitFrom(obj)); |
| } |
| |
| V8_INLINE bool IsBlackOrGrey(HeapObject obj) { |
| return Marking::IsBlackOrGrey<access_mode>(MarkBitFrom(obj)); |
| } |
| |
| V8_INLINE bool WhiteToGrey(HeapObject obj); |
| V8_INLINE bool WhiteToBlack(HeapObject obj); |
| V8_INLINE bool GreyToBlack(HeapObject obj); |
| |
| void ClearLiveness(MemoryChunk* chunk) { |
| static_cast<ConcreteState*>(this)->bitmap(chunk)->Clear(); |
| static_cast<ConcreteState*>(this)->SetLiveBytes(chunk, 0); |
| } |
| }; |
| |
| class MarkBitCellIterator { |
| public: |
| MarkBitCellIterator(MemoryChunk* chunk, Bitmap* bitmap) : chunk_(chunk) { |
| last_cell_index_ = |
| Bitmap::IndexToCell(chunk_->AddressToMarkbitIndex(chunk_->area_end())); |
| cell_base_ = chunk_->address(); |
| cell_index_ = |
| Bitmap::IndexToCell(chunk_->AddressToMarkbitIndex(cell_base_)); |
| cells_ = bitmap->cells(); |
| } |
| |
| inline bool Done() { return cell_index_ >= last_cell_index_; } |
| |
| inline bool HasNext() { return cell_index_ < last_cell_index_ - 1; } |
| |
| inline MarkBit::CellType* CurrentCell() { |
| DCHECK_EQ(cell_index_, Bitmap::IndexToCell(Bitmap::CellAlignIndex( |
| chunk_->AddressToMarkbitIndex(cell_base_)))); |
| return &cells_[cell_index_]; |
| } |
| |
| inline Address CurrentCellBase() { |
| DCHECK_EQ(cell_index_, Bitmap::IndexToCell(Bitmap::CellAlignIndex( |
| chunk_->AddressToMarkbitIndex(cell_base_)))); |
| return cell_base_; |
| } |
| |
| V8_WARN_UNUSED_RESULT inline bool Advance() { |
| cell_base_ += Bitmap::kBitsPerCell * kTaggedSize; |
| return ++cell_index_ != last_cell_index_; |
| } |
| |
| inline bool Advance(unsigned int new_cell_index) { |
| if (new_cell_index != cell_index_) { |
| DCHECK_GT(new_cell_index, cell_index_); |
| DCHECK_LE(new_cell_index, last_cell_index_); |
| unsigned int diff = new_cell_index - cell_index_; |
| cell_index_ = new_cell_index; |
| cell_base_ += diff * (Bitmap::kBitsPerCell * kTaggedSize); |
| return true; |
| } |
| return false; |
| } |
| |
| // Return the next mark bit cell. If there is no next it returns 0; |
| inline MarkBit::CellType PeekNext() { |
| if (HasNext()) { |
| return cells_[cell_index_ + 1]; |
| } |
| return 0; |
| } |
| |
| private: |
| MemoryChunk* chunk_; |
| MarkBit::CellType* cells_; |
| unsigned int last_cell_index_; |
| unsigned int cell_index_; |
| Address cell_base_; |
| }; |
| |
| enum LiveObjectIterationMode { |
| kBlackObjects, |
| kGreyObjects, |
| kAllLiveObjects |
| }; |
| |
| template <LiveObjectIterationMode mode> |
| class LiveObjectRange { |
| public: |
| class iterator { |
| public: |
| using value_type = std::pair<HeapObject, int /* size */>; |
| using pointer = const value_type*; |
| using reference = const value_type&; |
| using iterator_category = std::forward_iterator_tag; |
| |
| inline iterator(MemoryChunk* chunk, Bitmap* bitmap, Address start); |
| |
| inline iterator& operator++(); |
| inline iterator operator++(int); |
| |
| bool operator==(iterator other) const { |
| return current_object_ == other.current_object_; |
| } |
| |
| bool operator!=(iterator other) const { return !(*this == other); } |
| |
| value_type operator*() { |
| return std::make_pair(current_object_, current_size_); |
| } |
| |
| private: |
| inline void AdvanceToNextValidObject(); |
| |
| MemoryChunk* const chunk_; |
| Map const one_word_filler_map_; |
| Map const two_word_filler_map_; |
| Map const free_space_map_; |
| MarkBitCellIterator it_; |
| Address cell_base_; |
| MarkBit::CellType current_cell_; |
| HeapObject current_object_; |
| int current_size_; |
| }; |
| |
| LiveObjectRange(MemoryChunk* chunk, Bitmap* bitmap) |
| : chunk_(chunk), |
| bitmap_(bitmap), |
| start_(chunk_->area_start()), |
| end_(chunk->area_end()) { |
| DCHECK(!chunk->IsLargePage()); |
| } |
| |
| inline iterator begin(); |
| inline iterator end(); |
| |
| private: |
| MemoryChunk* const chunk_; |
| Bitmap* bitmap_; |
| Address start_; |
| Address end_; |
| }; |
| |
| class LiveObjectVisitor : AllStatic { |
| public: |
| enum IterationMode { |
| kKeepMarking, |
| kClearMarkbits, |
| }; |
| |
| // Visits black objects on a MemoryChunk until the Visitor returns |false| for |
| // an object. If IterationMode::kClearMarkbits is passed the markbits and |
| // slots for visited objects are cleared for each successfully visited object. |
| template <class Visitor, typename MarkingState> |
| static bool VisitBlackObjects(MemoryChunk* chunk, MarkingState* state, |
| Visitor* visitor, IterationMode iteration_mode, |
| HeapObject* failed_object); |
| |
| // Visits black objects on a MemoryChunk. The visitor is not allowed to fail |
| // visitation for an object. |
| template <class Visitor, typename MarkingState> |
| static void VisitBlackObjectsNoFail(MemoryChunk* chunk, MarkingState* state, |
| Visitor* visitor, |
| IterationMode iteration_mode); |
| |
| // Visits black objects on a MemoryChunk. The visitor is not allowed to fail |
| // visitation for an object. |
| template <class Visitor, typename MarkingState> |
| static void VisitGreyObjectsNoFail(MemoryChunk* chunk, MarkingState* state, |
| Visitor* visitor, |
| IterationMode iteration_mode); |
| |
| template <typename MarkingState> |
| static void RecomputeLiveBytes(MemoryChunk* chunk, MarkingState* state); |
| }; |
| |
| enum PageEvacuationMode { NEW_TO_NEW, NEW_TO_OLD }; |
| enum MarkingTreatmentMode { KEEP, CLEAR }; |
| enum class RememberedSetUpdatingMode { ALL, OLD_TO_NEW_ONLY }; |
| |
| // Base class for minor and full MC collectors. |
| class MarkCompactCollectorBase { |
| public: |
| static const int kMainThread = 0; |
| |
| virtual ~MarkCompactCollectorBase() = default; |
| |
| virtual void SetUp() = 0; |
| virtual void TearDown() = 0; |
| virtual void CollectGarbage() = 0; |
| |
| inline Heap* heap() const { return heap_; } |
| inline Isolate* isolate(); |
| |
| protected: |
| explicit MarkCompactCollectorBase(Heap* heap) |
| : heap_(heap), old_to_new_slots_(0) {} |
| |
| // Marking operations for objects reachable from roots. |
| virtual void MarkLiveObjects() = 0; |
| // Mark objects reachable (transitively) from objects in the marking |
| // work list. |
| virtual void ProcessMarkingWorklist() = 0; |
| // Clear non-live references held in side data structures. |
| virtual void ClearNonLiveReferences() = 0; |
| virtual void EvacuatePrologue() = 0; |
| virtual void EvacuateEpilogue() = 0; |
| virtual void Evacuate() = 0; |
| virtual void EvacuatePagesInParallel() = 0; |
| virtual void UpdatePointersAfterEvacuation() = 0; |
| virtual UpdatingItem* CreateToSpaceUpdatingItem(MemoryChunk* chunk, |
| Address start, |
| Address end) = 0; |
| virtual UpdatingItem* CreateRememberedSetUpdatingItem( |
| MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) = 0; |
| |
| template <class Evacuator, class Collector> |
| void CreateAndExecuteEvacuationTasks(Collector* collector, |
| ItemParallelJob* job, |
| MigrationObserver* migration_observer, |
| const intptr_t live_bytes); |
| |
| // Returns whether this page should be moved according to heuristics. |
| bool ShouldMovePage(Page* p, intptr_t live_bytes); |
| |
| int CollectToSpaceUpdatingItems(ItemParallelJob* job); |
| template <typename IterateableSpace> |
| int CollectRememberedSetUpdatingItems(ItemParallelJob* job, |
| IterateableSpace* space, |
| RememberedSetUpdatingMode mode); |
| |
| int NumberOfParallelCompactionTasks(int pages); |
| int NumberOfParallelPointerUpdateTasks(int pages, int slots); |
| int NumberOfParallelToSpacePointerUpdateTasks(int pages); |
| |
| Heap* heap_; |
| // Number of old to new slots. Should be computed during MarkLiveObjects. |
| // -1 indicates that the value couldn't be computed. |
| int old_to_new_slots_; |
| }; |
| |
| class MinorMarkingState final |
| : public MarkingStateBase<MinorMarkingState, AccessMode::ATOMIC> { |
| public: |
| ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) const { |
| return chunk->young_generation_bitmap<AccessMode::ATOMIC>(); |
| } |
| |
| void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by) { |
| chunk->young_generation_live_byte_count_ += by; |
| } |
| |
| intptr_t live_bytes(MemoryChunk* chunk) const { |
| return chunk->young_generation_live_byte_count_; |
| } |
| |
| void SetLiveBytes(MemoryChunk* chunk, intptr_t value) { |
| chunk->young_generation_live_byte_count_ = value; |
| } |
| }; |
| |
| class MinorNonAtomicMarkingState final |
| : public MarkingStateBase<MinorNonAtomicMarkingState, |
| AccessMode::NON_ATOMIC> { |
| public: |
| ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap( |
| const MemoryChunk* chunk) const { |
| return chunk->young_generation_bitmap<AccessMode::NON_ATOMIC>(); |
| } |
| |
| void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by) { |
| chunk->young_generation_live_byte_count_.fetch_add( |
| by, std::memory_order_relaxed); |
| } |
| |
| intptr_t live_bytes(MemoryChunk* chunk) const { |
| return chunk->young_generation_live_byte_count_.load( |
| std::memory_order_relaxed); |
| } |
| |
| void SetLiveBytes(MemoryChunk* chunk, intptr_t value) { |
| chunk->young_generation_live_byte_count_.store(value, |
| std::memory_order_relaxed); |
| } |
| }; |
| |
| // This marking state is used when concurrent marking is running. |
| class IncrementalMarkingState final |
| : public MarkingStateBase<IncrementalMarkingState, AccessMode::ATOMIC> { |
| public: |
| ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) const { |
| DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) - |
| reinterpret_cast<intptr_t>(chunk), |
| MemoryChunk::kMarkBitmapOffset); |
| return chunk->marking_bitmap<AccessMode::ATOMIC>(); |
| } |
| |
| // Concurrent marking uses local live bytes so we may do these accesses |
| // non-atomically. |
| void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by) { |
| chunk->live_byte_count_ += by; |
| } |
| |
| intptr_t live_bytes(MemoryChunk* chunk) const { |
| return chunk->live_byte_count_; |
| } |
| |
| void SetLiveBytes(MemoryChunk* chunk, intptr_t value) { |
| chunk->live_byte_count_ = value; |
| } |
| }; |
| |
| class MajorAtomicMarkingState final |
| : public MarkingStateBase<MajorAtomicMarkingState, AccessMode::ATOMIC> { |
| public: |
| ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) const { |
| DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) - |
| reinterpret_cast<intptr_t>(chunk), |
| MemoryChunk::kMarkBitmapOffset); |
| return chunk->marking_bitmap<AccessMode::ATOMIC>(); |
| } |
| |
| void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by) { |
| std::atomic_fetch_add( |
| reinterpret_cast<std::atomic<intptr_t>*>(&chunk->live_byte_count_), by); |
| } |
| }; |
| |
| class MajorNonAtomicMarkingState final |
| : public MarkingStateBase<MajorNonAtomicMarkingState, |
| AccessMode::NON_ATOMIC> { |
| public: |
| ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap( |
| const MemoryChunk* chunk) const { |
| DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) - |
| reinterpret_cast<intptr_t>(chunk), |
| MemoryChunk::kMarkBitmapOffset); |
| return chunk->marking_bitmap<AccessMode::NON_ATOMIC>(); |
| } |
| |
| void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by) { |
| chunk->live_byte_count_ += by; |
| } |
| |
| intptr_t live_bytes(MemoryChunk* chunk) const { |
| return chunk->live_byte_count_; |
| } |
| |
| void SetLiveBytes(MemoryChunk* chunk, intptr_t value) { |
| chunk->live_byte_count_ = value; |
| } |
| }; |
| |
| struct Ephemeron { |
| HeapObject key; |
| HeapObject value; |
| }; |
| |
| using EphemeronWorklist = Worklist<Ephemeron, 64>; |
| |
| // Weak objects encountered during marking. |
| struct WeakObjects { |
| Worklist<TransitionArray, 64> transition_arrays; |
| |
| // Keep track of all EphemeronHashTables in the heap to process |
| // them in the atomic pause. |
| Worklist<EphemeronHashTable, 64> ephemeron_hash_tables; |
| |
| // Keep track of all ephemerons for concurrent marking tasks. Only store |
| // ephemerons in these Worklists if both key and value are unreachable at the |
| // moment. |
| // |
| // MarkCompactCollector::ProcessEphemeronsUntilFixpoint drains and fills these |
| // worklists. |
| // |
| // current_ephemerons is used as draining worklist in the current fixpoint |
| // iteration. |
| EphemeronWorklist current_ephemerons; |
| |
| // Stores ephemerons to visit in the next fixpoint iteration. |
| EphemeronWorklist next_ephemerons; |
| |
| // When draining the marking worklist new discovered ephemerons are pushed |
| // into this worklist. |
| EphemeronWorklist discovered_ephemerons; |
| |
| // TODO(marja): For old space, we only need the slot, not the host |
| // object. Optimize this by adding a different storage for old space. |
| Worklist<std::pair<HeapObject, HeapObjectSlot>, 64> weak_references; |
| Worklist<std::pair<HeapObject, Code>, 64> weak_objects_in_code; |
| |
| Worklist<JSWeakRef, 64> js_weak_refs; |
| Worklist<WeakCell, 64> weak_cells; |
| |
| Worklist<SharedFunctionInfo, 64> bytecode_flushing_candidates; |
| Worklist<JSFunction, 64> flushed_js_functions; |
| }; |
| |
| struct EphemeronMarking { |
| std::vector<HeapObject> newly_discovered; |
| bool newly_discovered_overflowed; |
| size_t newly_discovered_limit; |
| }; |
| |
| // Collector for young and old generation. |
| class MarkCompactCollector final : public MarkCompactCollectorBase { |
| public: |
| #ifdef V8_CONCURRENT_MARKING |
| using MarkingState = IncrementalMarkingState; |
| #else |
| using MarkingState = MajorNonAtomicMarkingState; |
| #endif // V8_CONCURRENT_MARKING |
| |
| using NonAtomicMarkingState = MajorNonAtomicMarkingState; |
| |
| // Wrapper for the shared worklist. |
| class MarkingWorklist { |
| public: |
| using ConcurrentMarkingWorklist = Worklist<HeapObject, 64>; |
| using EmbedderTracingWorklist = Worklist<HeapObject, 16>; |
| |
| // The heap parameter is not used but needed to match the sequential case. |
| explicit MarkingWorklist(Heap* heap) {} |
| |
| void Push(HeapObject object) { |
| bool success = shared_.Push(kMainThread, object); |
| USE(success); |
| DCHECK(success); |
| } |
| |
| HeapObject Pop() { |
| HeapObject result; |
| if (shared_.Pop(kMainThread, &result)) return result; |
| #ifdef V8_CONCURRENT_MARKING |
| // The expectation is that this work list is empty almost all the time |
| // and we can thus avoid the emptiness checks by putting it last. |
| if (on_hold_.Pop(kMainThread, &result)) return result; |
| #endif |
| return HeapObject(); |
| } |
| |
| void Clear() { |
| shared_.Clear(); |
| on_hold_.Clear(); |
| embedder_.Clear(); |
| } |
| |
| bool IsEmpty() { |
| return shared_.IsLocalEmpty(kMainThread) && |
| on_hold_.IsLocalEmpty(kMainThread) && |
| shared_.IsGlobalPoolEmpty() && on_hold_.IsGlobalPoolEmpty(); |
| } |
| |
| bool IsEmbedderEmpty() { |
| return embedder_.IsLocalEmpty(kMainThread) && |
| embedder_.IsGlobalPoolEmpty(); |
| } |
| |
| int Size() { |
| return static_cast<int>(shared_.LocalSize(kMainThread) + |
| on_hold_.LocalSize(kMainThread)); |
| } |
| |
| // Calls the specified callback on each element of the deques and replaces |
| // the element with the result of the callback. If the callback returns |
| // nullptr then the element is removed from the deque. |
| // The callback must accept HeapObject and return HeapObject. |
| template <typename Callback> |
| void Update(Callback callback) { |
| shared_.Update(callback); |
| on_hold_.Update(callback); |
| embedder_.Update(callback); |
| } |
| |
| void ShareWorkIfGlobalPoolIsEmpty() { |
| if (!shared_.IsLocalEmpty(kMainThread) && shared_.IsGlobalPoolEmpty()) { |
| shared_.FlushToGlobal(kMainThread); |
| } |
| } |
| |
| ConcurrentMarkingWorklist* shared() { return &shared_; } |
| ConcurrentMarkingWorklist* on_hold() { return &on_hold_; } |
| EmbedderTracingWorklist* embedder() { return &embedder_; } |
| |
| void Print() { |
| PrintWorklist("shared", &shared_); |
| PrintWorklist("on_hold", &on_hold_); |
| } |
| |
| private: |
| // Prints the stats about the global pool of the worklist. |
| void PrintWorklist(const char* worklist_name, |
| ConcurrentMarkingWorklist* worklist); |
| |
| // Worklist used for most objects. |
| ConcurrentMarkingWorklist shared_; |
| |
| // Concurrent marking uses this worklist to bail out of marking objects |
| // in new space's linear allocation area. Used to avoid black allocation |
| // for new space. This allow the compiler to remove write barriers |
| // for freshly allocatd objects. |
| ConcurrentMarkingWorklist on_hold_; |
| |
| // Worklist for objects that potentially require embedder tracing, i.e., |
| // these objects need to be handed over to the embedder to find the full |
| // transitive closure. |
| EmbedderTracingWorklist embedder_; |
| }; |
| |
| class RootMarkingVisitor; |
| class CustomRootBodyMarkingVisitor; |
| |
| enum IterationMode { |
| kKeepMarking, |
| kClearMarkbits, |
| }; |
| |
| MarkingState* marking_state() { return &marking_state_; } |
| |
| NonAtomicMarkingState* non_atomic_marking_state() { |
| return &non_atomic_marking_state_; |
| } |
| |
| void SetUp() override; |
| void TearDown() override; |
| // Performs a global garbage collection. |
| void CollectGarbage() override; |
| |
| void CollectEvacuationCandidates(PagedSpace* space); |
| |
| void AddEvacuationCandidate(Page* p); |
| |
| // Prepares for GC by resetting relocation info in old and map spaces and |
| // choosing spaces to compact. |
| void Prepare(); |
| |
| // Stop concurrent marking (either by preempting it right away or waiting for |
| // it to complete as requested by |stop_request|). |
| void FinishConcurrentMarking(ConcurrentMarking::StopRequest stop_request); |
| |
| bool StartCompaction(); |
| |
| void AbortCompaction(); |
| |
| static inline bool IsOnEvacuationCandidate(Object obj) { |
| return Page::FromAddress(obj.ptr())->IsEvacuationCandidate(); |
| } |
| |
| static bool IsOnEvacuationCandidate(MaybeObject obj); |
| |
| struct RecordRelocSlotInfo { |
| MemoryChunk* memory_chunk; |
| SlotType slot_type; |
| bool should_record; |
| uint32_t offset; |
| }; |
| static RecordRelocSlotInfo PrepareRecordRelocSlot(Code host, RelocInfo* rinfo, |
| HeapObject target); |
| static void RecordRelocSlot(Code host, RelocInfo* rinfo, HeapObject target); |
| V8_INLINE static void RecordSlot(HeapObject object, ObjectSlot slot, |
| HeapObject target); |
| V8_INLINE static void RecordSlot(HeapObject object, HeapObjectSlot slot, |
| HeapObject target); |
| V8_INLINE static void RecordSlot(MemoryChunk* source_page, |
| HeapObjectSlot slot, HeapObject target); |
| void RecordLiveSlotsOnPage(Page* page); |
| |
| void UpdateSlots(SlotsBuffer* buffer); |
| void UpdateSlotsRecordedIn(SlotsBuffer* buffer); |
| |
| bool is_compacting() const { return compacting_; } |
| |
| // Ensures that sweeping is finished. |
| // |
| // Note: Can only be called safely from main thread. |
| V8_EXPORT_PRIVATE void EnsureSweepingCompleted(); |
| |
| // Checks if sweeping is in progress right now on any space. |
| bool sweeping_in_progress() const { return sweeper_->sweeping_in_progress(); } |
| |
| void set_evacuation(bool evacuation) { evacuation_ = evacuation; } |
| |
| bool evacuation() const { return evacuation_; } |
| |
| MarkingWorklist* marking_worklist() { return &marking_worklist_; } |
| |
| WeakObjects* weak_objects() { return &weak_objects_; } |
| |
| inline void AddTransitionArray(TransitionArray array); |
| |
| void AddEphemeronHashTable(EphemeronHashTable table) { |
| weak_objects_.ephemeron_hash_tables.Push(kMainThread, table); |
| } |
| |
| void AddEphemeron(HeapObject key, HeapObject value) { |
| weak_objects_.discovered_ephemerons.Push(kMainThread, |
| Ephemeron{key, value}); |
| } |
| |
| void AddWeakReference(HeapObject host, HeapObjectSlot slot) { |
| weak_objects_.weak_references.Push(kMainThread, std::make_pair(host, slot)); |
| } |
| |
| void AddWeakObjectInCode(HeapObject object, Code code) { |
| weak_objects_.weak_objects_in_code.Push(kMainThread, |
| std::make_pair(object, code)); |
| } |
| |
| void AddWeakRef(JSWeakRef weak_ref) { |
| weak_objects_.js_weak_refs.Push(kMainThread, weak_ref); |
| } |
| |
| void AddWeakCell(WeakCell weak_cell) { |
| weak_objects_.weak_cells.Push(kMainThread, weak_cell); |
| } |
| |
| inline void AddBytecodeFlushingCandidate(SharedFunctionInfo flush_candidate); |
| inline void AddFlushedJSFunction(JSFunction flushed_function); |
| |
| void AddNewlyDiscovered(HeapObject object) { |
| if (ephemeron_marking_.newly_discovered_overflowed) return; |
| |
| if (ephemeron_marking_.newly_discovered.size() < |
| ephemeron_marking_.newly_discovered_limit) { |
| ephemeron_marking_.newly_discovered.push_back(object); |
| } else { |
| ephemeron_marking_.newly_discovered_overflowed = true; |
| } |
| } |
| |
| void ResetNewlyDiscovered() { |
| ephemeron_marking_.newly_discovered_overflowed = false; |
| ephemeron_marking_.newly_discovered.clear(); |
| } |
| |
| Sweeper* sweeper() { return sweeper_; } |
| |
| #ifdef DEBUG |
| // Checks whether performing mark-compact collection. |
| bool in_use() { return state_ > PREPARE_GC; } |
| bool are_map_pointers_encoded() { return state_ == UPDATE_POINTERS; } |
| #endif |
| |
| void VerifyMarking(); |
| #ifdef VERIFY_HEAP |
| void VerifyValidStoreAndSlotsBufferEntries(); |
| void VerifyMarkbitsAreClean(); |
| void VerifyMarkbitsAreDirty(ReadOnlySpace* space); |
| void VerifyMarkbitsAreClean(PagedSpace* space); |
| void VerifyMarkbitsAreClean(NewSpace* space); |
| void VerifyMarkbitsAreClean(LargeObjectSpace* space); |
| #endif |
| |
| unsigned epoch() const { return epoch_; } |
| |
| explicit MarkCompactCollector(Heap* heap); |
| ~MarkCompactCollector() override; |
| |
| // Used by wrapper tracing. |
| V8_INLINE void MarkExternallyReferencedObject(HeapObject obj); |
| |
| private: |
| void ComputeEvacuationHeuristics(size_t area_size, |
| int* target_fragmentation_percent, |
| size_t* max_evacuated_bytes); |
| |
| void RecordObjectStats(); |
| |
| // Finishes GC, performs heap verification if enabled. |
| void Finish(); |
| |
| void MarkLiveObjects() override; |
| |
| // Marks the object black and adds it to the marking work list. |
| // This is for non-incremental marking only. |
| V8_INLINE void MarkObject(HeapObject host, HeapObject obj); |
| |
| // Marks the object black and adds it to the marking work list. |
| // This is for non-incremental marking only. |
| V8_INLINE void MarkRootObject(Root root, HeapObject obj); |
| |
| // Mark the heap roots and all objects reachable from them. |
| void MarkRoots(RootVisitor* root_visitor, |
| ObjectVisitor* custom_root_body_visitor); |
| |
| // Mark the string table specially. References to internalized strings from |
| // the string table are weak. |
| void MarkStringTable(ObjectVisitor* visitor); |
| |
| // Marks object reachable from harmony weak maps and wrapper tracing. |
| void ProcessEphemeronMarking(); |
| |
| // If the call-site of the top optimized code was not prepared for |
| // deoptimization, then treat embedded pointers in the code as strong as |
| // otherwise they can die and try to deoptimize the underlying code. |
| void ProcessTopOptimizedFrame(ObjectVisitor* visitor); |
| |
| // Drains the main thread marking work list. Will mark all pending objects |
| // if no concurrent threads are running. |
| void ProcessMarkingWorklist() override; |
| |
| enum class MarkingWorklistProcessingMode { |
| kDefault, |
| kTrackNewlyDiscoveredObjects |
| }; |
| |
| template <MarkingWorklistProcessingMode mode> |
| void ProcessMarkingWorklistInternal(); |
| |
| // Implements ephemeron semantics: Marks value if key is already reachable. |
| // Returns true if value was actually marked. |
| bool ProcessEphemeron(HeapObject key, HeapObject value); |
| |
| // Marks ephemerons and drains marking worklist iteratively |
| // until a fixpoint is reached. |
| void ProcessEphemeronsUntilFixpoint(); |
| |
| // Drains ephemeron and marking worklists. Single iteration of the |
| // fixpoint iteration. |
| bool ProcessEphemerons(); |
| |
| // Mark ephemerons and drain marking worklist with a linear algorithm. |
| // Only used if fixpoint iteration doesn't finish within a few iterations. |
| void ProcessEphemeronsLinear(); |
| |
| // Perform Wrapper Tracing if in use. |
| void PerformWrapperTracing(); |
| |
| // Callback function for telling whether the object *p is an unmarked |
| // heap object. |
| static bool IsUnmarkedHeapObject(Heap* heap, FullObjectSlot p); |
| |
| // Clear non-live references in weak cells, transition and descriptor arrays, |
| // and deoptimize dependent code of non-live maps. |
| void ClearNonLiveReferences() override; |
| void MarkDependentCodeForDeoptimization(); |
| // Checks if the given weak cell is a simple transition from the parent map |
| // of the given dead target. If so it clears the transition and trims |
| // the descriptor array of the parent if needed. |
| void ClearPotentialSimpleMapTransition(Map dead_target); |
| void ClearPotentialSimpleMapTransition(Map map, Map dead_target); |
| |
| // Flushes a weakly held bytecode array from a shared function info. |
| void FlushBytecodeFromSFI(SharedFunctionInfo shared_info); |
| |
| // Clears bytecode arrays that have not been executed for multiple |
| // collections. |
| void ClearOldBytecodeCandidates(); |
| |
| // Resets any JSFunctions which have had their bytecode flushed. |
| void ClearFlushedJsFunctions(); |
| |
| // Compact every array in the global list of transition arrays and |
| // trim the corresponding descriptor array if a transition target is non-live. |
| void ClearFullMapTransitions(); |
| void TrimDescriptorArray(Map map, DescriptorArray descriptors); |
| void TrimEnumCache(Map map, DescriptorArray descriptors); |
| bool CompactTransitionArray(Map map, TransitionArray transitions, |
| DescriptorArray descriptors); |
| |
| // After all reachable objects have been marked those weak map entries |
| // with an unreachable key are removed from all encountered weak maps. |
| // The linked list of all encountered weak maps is destroyed. |
| void ClearWeakCollections(); |
| |
| // Goes through the list of encountered weak references and clears those with |
| // dead values. If the value is a dead map and the parent map transitions to |
| // the dead map via weak cell, then this function also clears the map |
| // transition. |
| void ClearWeakReferences(); |
| |
| // Goes through the list of encountered JSWeakRefs and WeakCells and clears |
| // those with dead values. |
| void ClearJSWeakRefs(); |
| |
| void AbortWeakObjects(); |
| |
| // Starts sweeping of spaces by contributing on the main thread and setting |
| // up other pages for sweeping. Does not start sweeper tasks. |
| void StartSweepSpaces(); |
| void StartSweepSpace(PagedSpace* space); |
| |
| void EvacuatePrologue() override; |
| void EvacuateEpilogue() override; |
| void Evacuate() override; |
| void EvacuatePagesInParallel() override; |
| void UpdatePointersAfterEvacuation() override; |
| |
| UpdatingItem* CreateToSpaceUpdatingItem(MemoryChunk* chunk, Address start, |
| Address end) override; |
| UpdatingItem* CreateRememberedSetUpdatingItem( |
| MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) override; |
| |
| int CollectNewSpaceArrayBufferTrackerItems(ItemParallelJob* job); |
| int CollectOldSpaceArrayBufferTrackerItems(ItemParallelJob* job); |
| |
| void ReleaseEvacuationCandidates(); |
| void PostProcessEvacuationCandidates(); |
| void ReportAbortedEvacuationCandidate(HeapObject failed_object, |
| MemoryChunk* chunk); |
| |
| static const int kEphemeronChunkSize = 8 * KB; |
| |
| int NumberOfParallelEphemeronVisitingTasks(size_t elements); |
| |
| void RightTrimDescriptorArray(DescriptorArray array, int descriptors_to_trim); |
| |
| base::Mutex mutex_; |
| base::Semaphore page_parallel_job_semaphore_; |
| |
| #ifdef DEBUG |
| enum CollectorState { |
| IDLE, |
| PREPARE_GC, |
| MARK_LIVE_OBJECTS, |
| SWEEP_SPACES, |
| ENCODE_FORWARDING_ADDRESSES, |
| UPDATE_POINTERS, |
| RELOCATE_OBJECTS |
| }; |
| |
| // The current stage of the collector. |
| CollectorState state_; |
| #endif |
| |
| bool was_marked_incrementally_; |
| |
| bool evacuation_; |
| |
| // True if we are collecting slots to perform evacuation from evacuation |
| // candidates. |
| bool compacting_; |
| |
| bool black_allocation_; |
| |
| bool have_code_to_deoptimize_; |
| |
| MarkingWorklist marking_worklist_; |
| WeakObjects weak_objects_; |
| EphemeronMarking ephemeron_marking_; |
| |
| // Candidates for pages that should be evacuated. |
| std::vector<Page*> evacuation_candidates_; |
| // Pages that are actually processed during evacuation. |
| std::vector<Page*> old_space_evacuation_pages_; |
| std::vector<Page*> new_space_evacuation_pages_; |
| std::vector<std::pair<HeapObject, Page*>> aborted_evacuation_candidates_; |
| |
| Sweeper* sweeper_; |
| |
| MarkingState marking_state_; |
| NonAtomicMarkingState non_atomic_marking_state_; |
| |
| // Counts the number of major mark-compact collections. The counter is |
| // incremented right after marking. This is used for: |
| // - marking descriptor arrays. See NumberOfMarkedDescriptors. Only the lower |
| // two bits are used, so it is okay if this counter overflows and wraps |
| // around. |
| unsigned epoch_ = 0; |
| |
| friend class FullEvacuator; |
| friend class RecordMigratedSlotVisitor; |
| }; |
| |
| template <FixedArrayVisitationMode fixed_array_mode, |
| TraceRetainingPathMode retaining_path_mode, typename MarkingState> |
| class MarkingVisitor final |
| : public HeapVisitor< |
| int, |
| MarkingVisitor<fixed_array_mode, retaining_path_mode, MarkingState>> { |
| public: |
| using Parent = HeapVisitor< |
| int, MarkingVisitor<fixed_array_mode, retaining_path_mode, MarkingState>>; |
| |
| V8_INLINE MarkingVisitor(MarkCompactCollector* collector, |
| MarkingState* marking_state); |
| |
| V8_INLINE bool ShouldVisitMapPointer() { return false; } |
| |
| V8_INLINE int VisitBytecodeArray(Map map, BytecodeArray object); |
| V8_INLINE int VisitDescriptorArray(Map map, DescriptorArray object); |
| V8_INLINE int VisitEphemeronHashTable(Map map, EphemeronHashTable object); |
| V8_INLINE int VisitFixedArray(Map map, FixedArray object); |
| V8_INLINE int VisitJSApiObject(Map map, JSObject object); |
| V8_INLINE int VisitJSArrayBuffer(Map map, JSArrayBuffer object); |
| V8_INLINE int VisitJSFunction(Map map, JSFunction object); |
| V8_INLINE int VisitJSDataView(Map map, JSDataView object); |
| V8_INLINE int VisitJSTypedArray(Map map, JSTypedArray object); |
| V8_INLINE int VisitMap(Map map, Map object); |
| V8_INLINE int VisitSharedFunctionInfo(Map map, SharedFunctionInfo object); |
| V8_INLINE int VisitTransitionArray(Map map, TransitionArray object); |
| V8_INLINE int VisitWeakCell(Map map, WeakCell object); |
| V8_INLINE int VisitJSWeakRef(Map map, JSWeakRef object); |
| |
| // ObjectVisitor implementation. |
| V8_INLINE void VisitPointer(HeapObject host, ObjectSlot p) final { |
| VisitPointerImpl(host, p); |
| } |
| V8_INLINE void VisitPointer(HeapObject host, MaybeObjectSlot p) final { |
| VisitPointerImpl(host, p); |
| } |
| V8_INLINE void VisitPointers(HeapObject host, ObjectSlot start, |
| ObjectSlot end) final { |
| VisitPointersImpl(host, start, end); |
| } |
| V8_INLINE void VisitPointers(HeapObject host, MaybeObjectSlot start, |
| MaybeObjectSlot end) final { |
| VisitPointersImpl(host, start, end); |
| } |
| V8_INLINE void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final; |
| V8_INLINE void VisitCodeTarget(Code host, RelocInfo* rinfo) final; |
| |
| // Weak list pointers should be ignored during marking. The lists are |
| // reconstructed after GC. |
| void VisitCustomWeakPointers(HeapObject host, ObjectSlot start, |
| ObjectSlot end) final {} |
| |
| V8_INLINE void VisitDescriptors(DescriptorArray descriptors, |
| int number_of_own_descriptors); |
| // Marks the descriptor array black without pushing it on the marking work |
| // list and visits its header. |
| V8_INLINE void MarkDescriptorArrayBlack(HeapObject host, |
| DescriptorArray descriptors); |
| |
| private: |
| // Granularity in which FixedArrays are scanned if |fixed_array_mode| |
| // is true. |
| static const int kProgressBarScanningChunk = 32 * KB; |
| |
| template <typename TSlot> |
| V8_INLINE void VisitPointerImpl(HeapObject host, TSlot p); |
| |
| template <typename TSlot> |
| V8_INLINE void VisitPointersImpl(HeapObject host, TSlot start, TSlot end); |
| |
| V8_INLINE int VisitFixedArrayIncremental(Map map, FixedArray object); |
| |
| template <typename T> |
| V8_INLINE int VisitEmbedderTracingSubclass(Map map, T object); |
| |
| // Marks the object grey and pushes it on the marking work list. |
| V8_INLINE void MarkObject(HeapObject host, HeapObject obj); |
| |
| MarkingState* marking_state() { return marking_state_; } |
| |
| MarkCompactCollector::MarkingWorklist* marking_worklist() const { |
| return collector_->marking_worklist(); |
| } |
| |
| Heap* const heap_; |
| MarkCompactCollector* const collector_; |
| MarkingState* const marking_state_; |
| const unsigned mark_compact_epoch_; |
| }; |
| |
| class EvacuationScope { |
| public: |
| explicit EvacuationScope(MarkCompactCollector* collector) |
| : collector_(collector) { |
| collector_->set_evacuation(true); |
| } |
| |
| ~EvacuationScope() { collector_->set_evacuation(false); } |
| |
| private: |
| MarkCompactCollector* collector_; |
| }; |
| |
| #ifdef ENABLE_MINOR_MC |
| |
| // Collector for young-generation only. |
| class MinorMarkCompactCollector final : public MarkCompactCollectorBase { |
| public: |
| using MarkingState = MinorMarkingState; |
| using NonAtomicMarkingState = MinorNonAtomicMarkingState; |
| |
| explicit MinorMarkCompactCollector(Heap* heap); |
| ~MinorMarkCompactCollector() override; |
| |
| MarkingState* marking_state() { return &marking_state_; } |
| |
| NonAtomicMarkingState* non_atomic_marking_state() { |
| return &non_atomic_marking_state_; |
| } |
| |
| void SetUp() override; |
| void TearDown() override; |
| void CollectGarbage() override; |
| |
| void MakeIterable(Page* page, MarkingTreatmentMode marking_mode, |
| FreeSpaceTreatmentMode free_space_mode); |
| void CleanupSweepToIteratePages(); |
| |
| private: |
| using MarkingWorklist = Worklist<HeapObject, 64 /* segment size */>; |
| class RootMarkingVisitor; |
| |
| static const int kNumMarkers = 8; |
| static const int kMainMarker = 0; |
| |
| inline MarkingWorklist* worklist() { return worklist_; } |
| |
| inline YoungGenerationMarkingVisitor* main_marking_visitor() { |
| return main_marking_visitor_; |
| } |
| |
| void MarkLiveObjects() override; |
| void MarkRootSetInParallel(RootMarkingVisitor* root_visitor); |
| V8_INLINE void MarkRootObject(HeapObject obj); |
| void ProcessMarkingWorklist() override; |
| void ClearNonLiveReferences() override; |
| |
| void EvacuatePrologue() override; |
| void EvacuateEpilogue() override; |
| void Evacuate() override; |
| void EvacuatePagesInParallel() override; |
| void UpdatePointersAfterEvacuation() override; |
| |
| UpdatingItem* CreateToSpaceUpdatingItem(MemoryChunk* chunk, Address start, |
| Address end) override; |
| UpdatingItem* CreateRememberedSetUpdatingItem( |
| MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) override; |
| |
| int CollectNewSpaceArrayBufferTrackerItems(ItemParallelJob* job); |
| |
| int NumberOfParallelMarkingTasks(int pages); |
| |
| MarkingWorklist* worklist_; |
| |
| YoungGenerationMarkingVisitor* main_marking_visitor_; |
| base::Semaphore page_parallel_job_semaphore_; |
| std::vector<Page*> new_space_evacuation_pages_; |
| std::vector<Page*> sweep_to_iterate_pages_; |
| |
| MarkingState marking_state_; |
| NonAtomicMarkingState non_atomic_marking_state_; |
| |
| friend class YoungGenerationMarkingTask; |
| friend class YoungGenerationMarkingVisitor; |
| }; |
| |
| #endif // ENABLE_MINOR_MC |
| |
| } // namespace internal |
| } // namespace v8 |
| |
| #endif // V8_HEAP_MARK_COMPACT_H_ |