mark-compact.cc | Explore in Territory

// 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.

#include "src/heap/mark-compact.h"

#include <algorithm>
#include <atomic>
#include <iterator>
#include <memory>
#include <optional>
#include <unordered_map>
#include <unordered_set>

#include "src/base/bits.h"
#include "src/base/logging.h"
#include "src/base/platform/mutex.h"
#include "src/base/platform/platform.h"
#include "src/base/utils/random-number-generator.h"
#include "src/codegen/compilation-cache.h"
#include "src/common/assert-scope.h"
#include "src/common/globals.h"
#include "src/deoptimizer/deoptimizer.h"
#include "src/execution/execution.h"
#include "src/execution/frames-inl.h"
#include "src/execution/isolate-utils-inl.h"
#include "src/execution/isolate-utils.h"
#include "src/execution/vm-state-inl.h"
#include "src/flags/flags.h"
#include "src/handles/global-handles.h"
#include "src/heap/array-buffer-sweeper.h"
#include "src/heap/base/basic-slot-set.h"
#include "src/heap/concurrent-marking.h"
#include "src/heap/ephemeron-remembered-set.h"
#include "src/heap/evacuation-allocator-inl.h"
#include "src/heap/evacuation-verifier-inl.h"
#include "src/heap/gc-tracer-inl.h"
#include "src/heap/gc-tracer.h"
#include "src/heap/heap.h"
#include "src/heap/incremental-marking-inl.h"
#include "src/heap/index-generator.h"
#include "src/heap/large-spaces.h"
#include "src/heap/mark-compact-inl.h"
#include "src/heap/mark-sweep-utilities.h"
#include "src/heap/marking-barrier.h"
#include "src/heap/marking-inl.h"
#include "src/heap/marking-state-inl.h"
#include "src/heap/marking-visitor-inl.h"
#include "src/heap/marking.h"
#include "src/heap/memory-allocator.h"
#include "src/heap/memory-chunk-layout.h"
#include "src/heap/memory-chunk-metadata.h"
#include "src/heap/memory-measurement-inl.h"
#include "src/heap/memory-measurement.h"
#include "src/heap/mutable-page-metadata.h"
#include "src/heap/new-spaces.h"
#include "src/heap/object-stats.h"
#include "src/heap/objects-visiting-inl.h"
#include "src/heap/page-metadata-inl.h"
#include "src/heap/page-metadata.h"
#include "src/heap/parallel-work-item.h"
#include "src/heap/pretenuring-handler-inl.h"
#include "src/heap/pretenuring-handler.h"
#include "src/heap/read-only-heap.h"
#include "src/heap/read-only-spaces.h"
#include "src/heap/remembered-set.h"
#include "src/heap/safepoint.h"
#include "src/heap/slot-set.h"
#include "src/heap/spaces-inl.h"
#include "src/heap/sweeper.h"
#include "src/heap/traced-handles-marking-visitor.h"
#include "src/heap/weak-object-worklists.h"
#include "src/heap/zapping.h"
#include "src/init/v8.h"
#include "src/logging/tracing-flags.h"
#include "src/objects/embedder-data-array-inl.h"
#include "src/objects/foreign.h"
#include "src/objects/hash-table-inl.h"
#include "src/objects/heap-object-inl.h"
#include "src/objects/instance-type.h"
#include "src/objects/js-array-buffer-inl.h"
#include "src/objects/js-objects-inl.h"
#include "src/objects/maybe-object.h"
#include "src/objects/objects.h"
#include "src/objects/slots-inl.h"
#include "src/objects/smi.h"
#include "src/objects/string-forwarding-table-inl.h"
#include "src/objects/transitions-inl.h"
#include "src/objects/visitors.h"
#include "src/snapshot/shared-heap-serializer.h"
#include "src/tasks/cancelable-task.h"
#include "src/tracing/tracing-category-observer.h"
#include "src/utils/utils-inl.h"

namespace v8 {
namespace internal {

// =============================================================================
// Verifiers
// =============================================================================

#ifdef VERIFY_HEAP
namespace {

class FullMarkingVerifier : public MarkingVerifierBase { … };

}  // namespace
#endif  // VERIFY_HEAP

// ==================================================================
// MarkCompactCollector
// ==================================================================

namespace {

int NumberOfAvailableCores() { … }

int NumberOfParallelCompactionTasks(Heap* heap) { … }

}  // namespace

// This visitor is used for marking on the main thread. It is cheaper than
// the concurrent marking visitor because it does not snapshot JSObjects.
class MainMarkingVisitor final
    : public FullMarkingVisitorBase<MainMarkingVisitor> { … };

MarkCompactCollector::MarkCompactCollector(Heap* heap)
    : … { … }

MarkCompactCollector::~MarkCompactCollector() = default;

void MarkCompactCollector::TearDown() { … }

void MarkCompactCollector::AddEvacuationCandidate(PageMetadata* p) { … }

static void TraceFragmentation(PagedSpace* space) { … }

bool MarkCompactCollector::StartCompaction(StartCompactionMode mode) { … }

void MarkCompactCollector::StartMarking() { … }

void MarkCompactCollector::MaybeEnableBackgroundThreadsInCycle(
    CallOrigin origin) { … }

void MarkCompactCollector::CollectGarbage() { … }

#ifdef VERIFY_HEAP

void MarkCompactCollector::VerifyMarkbitsAreClean(PagedSpaceBase* space) { … }

void MarkCompactCollector::VerifyMarkbitsAreClean(NewSpace* space) { … }

void MarkCompactCollector::VerifyMarkbitsAreClean(LargeObjectSpace* space) { … }

void MarkCompactCollector::VerifyMarkbitsAreClean() { … }

#endif  // VERIFY_HEAP

void MarkCompactCollector::ComputeEvacuationHeuristics(
    size_t area_size, int* target_fragmentation_percent,
    size_t* max_evacuated_bytes) { … }

void MarkCompactCollector::CollectEvacuationCandidates(PagedSpace* space) { … }

void MarkCompactCollector::Prepare() { … }

void MarkCompactCollector::FinishConcurrentMarking() { … }

void MarkCompactCollector::VerifyMarking() { … }

namespace {

void ShrinkPagesToObjectSizes(Heap* heap, OldLargeObjectSpace* space) { … }

}  // namespace

void MarkCompactCollector::Finish() { … }

void MarkCompactCollector::SweepArrayBufferExtensions() { … }

// This visitor is used to visit the body of special objects held alive by
// other roots.
//
// It is currently used for
// - InstructionStream held alive by the top optimized frame. This code cannot
// be deoptimized and thus have to be kept alive in an isolate way, i.e., it
// should not keep alive other code objects reachable through the weak list but
// they should keep alive its embedded pointers (which would otherwise be
// dropped).
// - Prefix of the string table.
// - If V8_ENABLE_SANDBOX, client Isolates' waiter queue node
// ExternalPointer_t in shared Isolates.
class MarkCompactCollector::CustomRootBodyMarkingVisitor final
    : public ObjectVisitorWithCageBases { … };

class MarkCompactCollector::SharedHeapObjectVisitor final
    : public ObjectVisitorWithCageBases { … };

class InternalizedStringTableCleaner final : public RootVisitor { … };

#ifdef V8_ENABLE_SANDBOX
class MarkExternalPointerFromExternalStringTable : public RootVisitor { … };
#endif

// Implementation of WeakObjectRetainer for mark compact GCs. All marked objects
// are retained.
class MarkCompactWeakObjectRetainer : public WeakObjectRetainer { … };

class RecordMigratedSlotVisitor : public ObjectVisitorWithCageBases { … };

class MigrationObserver { … };

class ProfilingMigrationObserver final : public MigrationObserver { … };

class HeapObjectVisitor { … };

class EvacuateVisitorBase : public HeapObjectVisitor { … };

class EvacuateNewSpaceVisitor final : public EvacuateVisitorBase { … };

class EvacuateNewToOldSpacePageVisitor final : public HeapObjectVisitor { … };

class EvacuateOldSpaceVisitor final : public EvacuateVisitorBase { … };

class EvacuateRecordOnlyVisitor final : public HeapObjectVisitor { … };

// static
bool MarkCompactCollector::IsUnmarkedHeapObject(Heap* heap, FullObjectSlot p) { … }

// static
bool MarkCompactCollector::IsUnmarkedSharedHeapObject(Heap* heap,
                                                      FullObjectSlot p) { … }

void MarkCompactCollector::MarkRoots(RootVisitor* root_visitor) { … }

void MarkCompactCollector::MarkRootsFromConservativeStack(
    RootVisitor* root_visitor) { … }

void MarkCompactCollector::MarkObjectsFromClientHeaps() { … }

void MarkCompactCollector::MarkObjectsFromClientHeap(Isolate* client) { … }

bool MarkCompactCollector::MarkTransitiveClosureUntilFixpoint() { … }

bool MarkCompactCollector::ProcessEphemerons() { … }

void MarkCompactCollector::MarkTransitiveClosureLinear() { … }

void MarkCompactCollector::PerformWrapperTracing() { … }

namespace {

constexpr size_t kDeadlineCheckInterval = …;

}  // namespace

std::pair<size_t, size_t> MarkCompactCollector::ProcessMarkingWorklist(
    v8::base::TimeDelta max_duration, size_t max_bytes_to_process,
    MarkingWorklistProcessingMode mode) { … }

bool MarkCompactCollector::ProcessEphemeron(Tagged<HeapObject> key,
                                            Tagged<HeapObject> value) { … }

void MarkCompactCollector::VerifyEphemeronMarking() { … }

void MarkCompactCollector::MarkTransitiveClosure() { … }

void MarkCompactCollector::ProcessTopOptimizedFrame(ObjectVisitor* visitor,
                                                    Isolate* isolate) { … }

void MarkCompactCollector::RecordObjectStats() { … }

namespace {

bool ShouldRetainMap(MarkingState* marking_state, Tagged<Map> map, int age) { … }

}  // namespace

void MarkCompactCollector::RetainMaps() { … }

void MarkCompactCollector::MarkLiveObjects() { … }

namespace {

class ParallelClearingJob final : public v8::JobTask { … };

class ClearStringTableJobItem final : public ParallelClearingJob::ClearingItem { … };

}  // namespace

class FullStringForwardingTableCleaner final
    : public StringForwardingTableCleanerBase { … };

namespace {

class SharedStructTypeRegistryCleaner final : public RootVisitor { … };

class ClearSharedStructTypeRegistryJobItem final
    : public ParallelClearingJob::ClearingItem { … };

}  // namespace

class MarkCompactCollector::ClearTrivialWeakRefJobItem final
    : public ParallelClearingJob::ClearingItem { … };

class MarkCompactCollector::FilterNonTrivialWeakRefJobItem final
    : public ParallelClearingJob::ClearingItem { … };

void MarkCompactCollector::ClearNonLiveReferences() { … }

void MarkCompactCollector::MarkDependentCodeForDeoptimization() { … }

void MarkCompactCollector::ClearPotentialSimpleMapTransition(
    Tagged<Map> dead_target) { … }

void MarkCompactCollector::ClearPotentialSimpleMapTransition(
    Tagged<Map> map, Tagged<Map> dead_target) { … }

bool MarkCompactCollector::SpecialClearMapSlot(Tagged<HeapObject> host,
                                               Tagged<Map> map,
                                               HeapObjectSlot slot) { … }

void MarkCompactCollector::FlushBytecodeFromSFI(
    Tagged<SharedFunctionInfo> shared_info) { … }

void MarkCompactCollector::ProcessOldCodeCandidates() { … }

bool MarkCompactCollector::ProcessOldBytecodeSFI(
    Tagged<SharedFunctionInfo> flushing_candidate) { … }

bool MarkCompactCollector::ProcessOldBaselineSFI(
    Tagged<SharedFunctionInfo> flushing_candidate) { … }

void MarkCompactCollector::FlushSFI(Tagged<SharedFunctionInfo> sfi,
                                    bool bytecode_already_decompiled) { … }

void MarkCompactCollector::ClearFlushedJsFunctions() { … }

void MarkCompactCollector::ProcessFlushedBaselineCandidates() { … }

void MarkCompactCollector::ClearFullMapTransitions() { … }

// Returns false if no maps have died, or if the transition array is
// still being deserialized.
bool MarkCompactCollector::TransitionArrayNeedsCompaction(
    Tagged<TransitionArray> transitions, int num_transitions) { … }

bool MarkCompactCollector::CompactTransitionArray(
    Tagged<Map> map, Tagged<TransitionArray> transitions,
    Tagged<DescriptorArray> descriptors) { … }

void MarkCompactCollector::RightTrimDescriptorArray(
    Tagged<DescriptorArray> array, int descriptors_to_trim) { … }

void MarkCompactCollector::RecordStrongDescriptorArraysForWeakening(
    GlobalHandleVector<DescriptorArray> strong_descriptor_arrays) { … }

void MarkCompactCollector::WeakenStrongDescriptorArrays() { … }

void MarkCompactCollector::TrimDescriptorArray(
    Tagged<Map> map, Tagged<DescriptorArray> descriptors) { … }

void MarkCompactCollector::TrimEnumCache(Tagged<Map> map,
                                         Tagged<DescriptorArray> descriptors) { … }

void MarkCompactCollector::ClearWeakCollections() { … }

void MarkCompactCollector::ClearTrivialWeakReferences() { … }

void MarkCompactCollector::FilterNonTrivialWeakReferences() { … }

void MarkCompactCollector::ClearNonTrivialWeakReferences() { … }

void MarkCompactCollector::ClearJSWeakRefs() { … }

// static
bool MarkCompactCollector::ShouldRecordRelocSlot(Tagged<InstructionStream> host,
                                                 RelocInfo* rinfo,
                                                 Tagged<HeapObject> target) { … }

// static
MarkCompactCollector::RecordRelocSlotInfo
MarkCompactCollector::ProcessRelocInfo(Tagged<InstructionStream> host,
                                       RelocInfo* rinfo,
                                       Tagged<HeapObject> target) { … }

// static
void MarkCompactCollector::RecordRelocSlot(Tagged<InstructionStream> host,
                                           RelocInfo* rinfo,
                                           Tagged<HeapObject> target) { … }

namespace {

// Missing specialization MakeSlotValue<FullObjectSlot, WEAK>() will turn
// attempt to store a weak reference to strong-only slot to a compilation error.
template <typename TSlot, HeapObjectReferenceType reference_type>
typename TSlot::TObject MakeSlotValue(Tagged<HeapObject> heap_object);

template <>
Tagged<Object> MakeSlotValue<ObjectSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }

template <>
Tagged<MaybeObject>
MakeSlotValue<MaybeObjectSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }

template <>
Tagged<MaybeObject>
MakeSlotValue<MaybeObjectSlot, HeapObjectReferenceType::WEAK>(
    Tagged<HeapObject> heap_object) { … }

template <>
Tagged<Object>
MakeSlotValue<WriteProtectedSlot<ObjectSlot>, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }

#ifdef V8_ENABLE_SANDBOX
template <>
Tagged<Object> MakeSlotValue<WriteProtectedSlot<ProtectedPointerSlot>,
                             HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }
#endif

template <>
Tagged<Object>
MakeSlotValue<OffHeapObjectSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }

#ifdef V8_COMPRESS_POINTERS
template <>
Tagged<Object> MakeSlotValue<FullObjectSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }

template <>
Tagged<MaybeObject>
MakeSlotValue<FullMaybeObjectSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }

template <>
Tagged<MaybeObject>
MakeSlotValue<FullMaybeObjectSlot, HeapObjectReferenceType::WEAK>(
    Tagged<HeapObject> heap_object) { … }

#ifdef V8_EXTERNAL_CODE_SPACE
template <>
Tagged<Object>
MakeSlotValue<InstructionStreamSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }
#endif  // V8_EXTERNAL_CODE_SPACE

#ifdef V8_ENABLE_SANDBOX
template <>
Tagged<Object>
MakeSlotValue<ProtectedPointerSlot, HeapObjectReferenceType::STRONG>(
    Tagged<HeapObject> heap_object) { … }
#endif  // V8_ENABLE_SANDBOX

// The following specialization
//   MakeSlotValue<FullMaybeObjectSlot, HeapObjectReferenceType::WEAK>()
// is not used.
#endif  // V8_COMPRESS_POINTERS

template <HeapObjectReferenceType reference_type, typename TSlot>
static inline void UpdateSlot(PtrComprCageBase cage_base, TSlot slot,
                              Tagged<HeapObject> heap_obj) { … }

template <typename TSlot>
static inline void UpdateSlot(PtrComprCageBase cage_base, TSlot slot) { … }

template <typename TSlot>
static inline SlotCallbackResult UpdateOldToSharedSlot(
    PtrComprCageBase cage_base, TSlot slot) { … }

template <typename TSlot>
static inline void UpdateStrongSlot(PtrComprCageBase cage_base, TSlot slot) { … }

static inline SlotCallbackResult UpdateStrongOldToSharedSlot(
    PtrComprCageBase cage_base, FullMaybeObjectSlot slot) { … }

static inline void UpdateStrongCodeSlot(Tagged<HeapObject> host,
                                        PtrComprCageBase cage_base,
                                        PtrComprCageBase code_cage_base,
                                        InstructionStreamSlot slot) { … }

}  // namespace

// Visitor for updating root pointers and to-space pointers.
// It does not expect to encounter pointers to dead objects.
class PointersUpdatingVisitor final : public ObjectVisitorWithCageBases,
                                      public RootVisitor { … };

static Tagged<String> UpdateReferenceInExternalStringTableEntry(
    Heap* heap, FullObjectSlot p) { … }

void MarkCompactCollector::EvacuatePrologue() { … }

void MarkCompactCollector::EvacuateEpilogue() { … }

class Evacuator final : public Malloced { … };

void Evacuator::EvacuatePage(MutablePageMetadata* page) { … }

void Evacuator::Finalize() { … }

class LiveObjectVisitor final : AllStatic { … };

template <class Visitor>
bool LiveObjectVisitor::VisitMarkedObjects(PageMetadata* page, Visitor* visitor,
                                           Tagged<HeapObject>* failed_object) { … }

template <class Visitor>
void LiveObjectVisitor::VisitMarkedObjectsNoFail(PageMetadata* page,
                                                 Visitor* visitor) { … }

bool Evacuator::RawEvacuatePage(MutablePageMetadata* page) { … }

class PageEvacuationJob : public v8::JobTask { … };

namespace {
size_t CreateAndExecuteEvacuationTasks(
    Heap* heap, MarkCompactCollector* collector,
    std::vector<std::pair<ParallelWorkItem, MutablePageMetadata*>>
        evacuation_items) { … }

enum class MemoryReductionMode { … };

// NewSpacePages with more live bytes than this threshold qualify for fast
// evacuation.
intptr_t NewSpacePageEvacuationThreshold() { … }

bool ShouldMovePage(PageMetadata* p, intptr_t live_bytes,
                    MemoryReductionMode memory_reduction_mode) { … }

void TraceEvacuation(Isolate* isolate, size_t pages_count,
                     size_t wanted_num_tasks, size_t live_bytes,
                     size_t aborted_pages) { … }

}  // namespace

void MarkCompactCollector::EvacuatePagesInParallel() { … }

class EvacuationWeakObjectRetainer : public WeakObjectRetainer { … };

void MarkCompactCollector::Evacuate() { … }

class UpdatingItem : public ParallelWorkItem { … };

class PointersUpdatingJob : public v8::JobTask { … };

namespace {

class RememberedSetUpdatingItem : public UpdatingItem { … };

}  // namespace

namespace {
template <typename IterateableSpace>
void CollectRememberedSetUpdatingItems(
    std::vector<std::unique_ptr<UpdatingItem>>* items,
    IterateableSpace* space) { … }
}  // namespace

class EphemeronTableUpdatingItem : public UpdatingItem { … };

void MarkCompactCollector::UpdatePointersAfterEvacuation() { … }

void MarkCompactCollector::UpdatePointersInClientHeaps() { … }

void MarkCompactCollector::UpdatePointersInClientHeap(Isolate* client) { … }

void MarkCompactCollector::UpdatePointersInPointerTables() { … }

void MarkCompactCollector::ReportAbortedEvacuationCandidateDueToOOM(
    Address failed_start, PageMetadata* page) { … }

void MarkCompactCollector::ReportAbortedEvacuationCandidateDueToFlags(
    Address failed_start, PageMetadata* page) { … }

namespace {

void ReRecordPage(Heap* heap, Address failed_start, PageMetadata* page) { … }

}  // namespace

size_t MarkCompactCollector::PostProcessAbortedEvacuationCandidates() { … }

void MarkCompactCollector::ReleaseEvacuationCandidates() { … }

void MarkCompactCollector::StartSweepNewSpace() { … }

void MarkCompactCollector::StartSweepSpace(PagedSpace* space) { … }

namespace {
bool ShouldPostponeFreeingEmptyPages(LargeObjectSpace* space) { … }
}  // namespace

void MarkCompactCollector::SweepLargeSpace(LargeObjectSpace* space) { … }

void MarkCompactCollector::Sweep() { … }

RootMarkingVisitor::RootMarkingVisitor(MarkCompactCollector* collector)
    : … { … }

RootMarkingVisitor::~RootMarkingVisitor() = default;

void RootMarkingVisitor::VisitRunningCode(
    FullObjectSlot code_slot, FullObjectSlot istream_or_smi_zero_slot) { … }

}  // namespace internal
}  // namespace v8
chromium/v8/src/heap/mark-compact.cc
