blob: 91a19021821065f974b2f007798a5c848e87ba0b [file] [log] [blame]
// 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 <unordered_map>
#include "src/base/optional.h"
#include "src/base/utils/random-number-generator.h"
#include "src/codegen/compilation-cache.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/handles/global-handles.h"
#include "src/heap/array-buffer-sweeper.h"
#include "src/heap/code-object-registry.h"
#include "src/heap/gc-tracer.h"
#include "src/heap/incremental-marking-inl.h"
#include "src/heap/index-generator.h"
#include "src/heap/invalidated-slots-inl.h"
#include "src/heap/item-parallel-job.h"
#include "src/heap/large-spaces.h"
#include "src/heap/local-allocator-inl.h"
#include "src/heap/mark-compact-inl.h"
#include "src/heap/marking-barrier.h"
#include "src/heap/marking-visitor-inl.h"
#include "src/heap/marking-visitor.h"
#include "src/heap/memory-measurement-inl.h"
#include "src/heap/memory-measurement.h"
#include "src/heap/object-stats.h"
#include "src/heap/objects-visiting-inl.h"
#include "src/heap/parallel-work-item.h"
#include "src/heap/read-only-heap.h"
#include "src/heap/read-only-spaces.h"
#include "src/heap/safepoint.h"
#include "src/heap/spaces-inl.h"
#include "src/heap/sweeper.h"
#include "src/heap/worklist.h"
#include "src/ic/stub-cache.h"
#include "src/init/v8.h"
#include "src/objects/embedder-data-array-inl.h"
#include "src/objects/foreign.h"
#include "src/objects/hash-table-inl.h"
#include "src/objects/js-objects-inl.h"
#include "src/objects/maybe-object.h"
#include "src/objects/slots-inl.h"
#include "src/objects/transitions-inl.h"
#include "src/tasks/cancelable-task.h"
#include "src/utils/utils-inl.h"
namespace v8 {
namespace internal {
const char* Marking::kWhiteBitPattern = "00";
const char* Marking::kBlackBitPattern = "11";
const char* Marking::kGreyBitPattern = "10";
const char* Marking::kImpossibleBitPattern = "01";
// The following has to hold in order for {MarkingState::MarkBitFrom} to not
// produce invalid {kImpossibleBitPattern} in the marking bitmap by overlapping.
STATIC_ASSERT(Heap::kMinObjectSizeInTaggedWords >= 2);
// =============================================================================
// Verifiers
// =============================================================================
#ifdef VERIFY_HEAP
namespace {
class MarkingVerifier : public ObjectVisitor, public RootVisitor {
public:
virtual void Run() = 0;
protected:
explicit MarkingVerifier(Heap* heap) : heap_(heap) {}
virtual ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap(
const MemoryChunk* chunk) = 0;
virtual void VerifyPointers(ObjectSlot start, ObjectSlot end) = 0;
virtual void VerifyPointers(MaybeObjectSlot start, MaybeObjectSlot end) = 0;
virtual void VerifyRootPointers(FullObjectSlot start, FullObjectSlot end) = 0;
virtual bool IsMarked(HeapObject object) = 0;
virtual bool IsBlackOrGrey(HeapObject object) = 0;
void VisitPointers(HeapObject host, ObjectSlot start,
ObjectSlot end) override {
VerifyPointers(start, end);
}
void VisitPointers(HeapObject host, MaybeObjectSlot start,
MaybeObjectSlot end) override {
VerifyPointers(start, end);
}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) override {
VerifyRootPointers(start, end);
}
void VerifyRoots();
void VerifyMarkingOnPage(const Page* page, Address start, Address end);
void VerifyMarking(NewSpace* new_space);
void VerifyMarking(PagedSpace* paged_space);
void VerifyMarking(LargeObjectSpace* lo_space);
Heap* heap_;
};
void MarkingVerifier::VerifyRoots() {
heap_->IterateRoots(this, base::EnumSet<SkipRoot>{SkipRoot::kWeak});
}
void MarkingVerifier::VerifyMarkingOnPage(const Page* page, Address start,
Address end) {
Address next_object_must_be_here_or_later = start;
for (auto object_and_size :
LiveObjectRange<kAllLiveObjects>(page, bitmap(page))) {
HeapObject object = object_and_size.first;
size_t size = object_and_size.second;
Address current = object.address();
if (current < start) continue;
if (current >= end) break;
CHECK(IsMarked(object));
CHECK(current >= next_object_must_be_here_or_later);
object.Iterate(this);
next_object_must_be_here_or_later = current + size;
// The object is either part of a black area of black allocation or a
// regular black object
CHECK(bitmap(page)->AllBitsSetInRange(
page->AddressToMarkbitIndex(current),
page->AddressToMarkbitIndex(next_object_must_be_here_or_later)) ||
bitmap(page)->AllBitsClearInRange(
page->AddressToMarkbitIndex(current + kTaggedSize * 2),
page->AddressToMarkbitIndex(next_object_must_be_here_or_later)));
current = next_object_must_be_here_or_later;
}
}
void MarkingVerifier::VerifyMarking(NewSpace* space) {
Address end = space->top();
// The bottom position is at the start of its page. Allows us to use
// page->area_start() as start of range on all pages.
CHECK_EQ(space->first_allocatable_address(),
space->first_page()->area_start());
PageRange range(space->first_allocatable_address(), end);
for (auto it = range.begin(); it != range.end();) {
Page* page = *(it++);
Address limit = it != range.end() ? page->area_end() : end;
CHECK(limit == end || !page->Contains(end));
VerifyMarkingOnPage(page, page->area_start(), limit);
}
}
void MarkingVerifier::VerifyMarking(PagedSpace* space) {
for (Page* p : *space) {
VerifyMarkingOnPage(p, p->area_start(), p->area_end());
}
}
void MarkingVerifier::VerifyMarking(LargeObjectSpace* lo_space) {
LargeObjectSpaceObjectIterator it(lo_space);
for (HeapObject obj = it.Next(); !obj.is_null(); obj = it.Next()) {
if (IsBlackOrGrey(obj)) {
obj.Iterate(this);
}
}
}
class FullMarkingVerifier : public MarkingVerifier {
public:
explicit FullMarkingVerifier(Heap* heap)
: MarkingVerifier(heap),
marking_state_(
heap->mark_compact_collector()->non_atomic_marking_state()) {}
void Run() override {
VerifyRoots();
VerifyMarking(heap_->new_space());
VerifyMarking(heap_->new_lo_space());
VerifyMarking(heap_->old_space());
VerifyMarking(heap_->code_space());
VerifyMarking(heap_->map_space());
VerifyMarking(heap_->lo_space());
VerifyMarking(heap_->code_lo_space());
}
protected:
ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap(
const MemoryChunk* chunk) override {
return marking_state_->bitmap(chunk);
}
bool IsMarked(HeapObject object) override {
return marking_state_->IsBlack(object);
}
bool IsBlackOrGrey(HeapObject object) override {
return marking_state_->IsBlackOrGrey(object);
}
void VerifyPointers(ObjectSlot start, ObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VerifyPointers(MaybeObjectSlot start, MaybeObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VerifyRootPointers(FullObjectSlot start, FullObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
VerifyHeapObjectImpl(target);
}
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
DCHECK(RelocInfo::IsEmbeddedObjectMode(rinfo->rmode()));
if (!host.IsWeakObject(rinfo->target_object())) {
HeapObject object = rinfo->target_object();
VerifyHeapObjectImpl(object);
}
}
private:
V8_INLINE void VerifyHeapObjectImpl(HeapObject heap_object) {
CHECK(marking_state_->IsBlackOrGrey(heap_object));
}
template <typename TSlot>
V8_INLINE void VerifyPointersImpl(TSlot start, TSlot end) {
for (TSlot slot = start; slot < end; ++slot) {
typename TSlot::TObject object = *slot;
HeapObject heap_object;
if (object.GetHeapObjectIfStrong(&heap_object)) {
VerifyHeapObjectImpl(heap_object);
}
}
}
MarkCompactCollector::NonAtomicMarkingState* marking_state_;
};
class EvacuationVerifier : public ObjectVisitor, public RootVisitor {
public:
virtual void Run() = 0;
void VisitPointers(HeapObject host, ObjectSlot start,
ObjectSlot end) override {
VerifyPointers(start, end);
}
void VisitPointers(HeapObject host, MaybeObjectSlot start,
MaybeObjectSlot end) override {
VerifyPointers(start, end);
}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) override {
VerifyRootPointers(start, end);
}
protected:
explicit EvacuationVerifier(Heap* heap) : heap_(heap) {}
inline Heap* heap() { return heap_; }
virtual void VerifyPointers(ObjectSlot start, ObjectSlot end) = 0;
virtual void VerifyPointers(MaybeObjectSlot start, MaybeObjectSlot end) = 0;
virtual void VerifyRootPointers(FullObjectSlot start, FullObjectSlot end) = 0;
void VerifyRoots();
void VerifyEvacuationOnPage(Address start, Address end);
void VerifyEvacuation(NewSpace* new_space);
void VerifyEvacuation(PagedSpace* paged_space);
Heap* heap_;
};
void EvacuationVerifier::VerifyRoots() {
heap_->IterateRoots(this, base::EnumSet<SkipRoot>{SkipRoot::kWeak});
}
void EvacuationVerifier::VerifyEvacuationOnPage(Address start, Address end) {
Address current = start;
while (current < end) {
HeapObject object = HeapObject::FromAddress(current);
if (!object.IsFreeSpaceOrFiller()) object.Iterate(this);
current += object.Size();
}
}
void EvacuationVerifier::VerifyEvacuation(NewSpace* space) {
PageRange range(space->first_allocatable_address(), space->top());
for (auto it = range.begin(); it != range.end();) {
Page* page = *(it++);
Address current = page->area_start();
Address limit = it != range.end() ? page->area_end() : space->top();
CHECK(limit == space->top() || !page->Contains(space->top()));
VerifyEvacuationOnPage(current, limit);
}
}
void EvacuationVerifier::VerifyEvacuation(PagedSpace* space) {
for (Page* p : *space) {
if (p->IsEvacuationCandidate()) continue;
if (p->Contains(space->top())) {
CodePageMemoryModificationScope memory_modification_scope(p);
heap_->CreateFillerObjectAt(
space->top(), static_cast<int>(space->limit() - space->top()),
ClearRecordedSlots::kNo);
}
VerifyEvacuationOnPage(p->area_start(), p->area_end());
}
}
class FullEvacuationVerifier : public EvacuationVerifier {
public:
explicit FullEvacuationVerifier(Heap* heap) : EvacuationVerifier(heap) {}
void Run() override {
VerifyRoots();
VerifyEvacuation(heap_->new_space());
VerifyEvacuation(heap_->old_space());
VerifyEvacuation(heap_->code_space());
VerifyEvacuation(heap_->map_space());
}
protected:
V8_INLINE void VerifyHeapObjectImpl(HeapObject heap_object) {
CHECK_IMPLIES(Heap::InYoungGeneration(heap_object),
Heap::InToPage(heap_object));
CHECK(!MarkCompactCollector::IsOnEvacuationCandidate(heap_object));
}
template <typename TSlot>
void VerifyPointersImpl(TSlot start, TSlot end) {
for (TSlot current = start; current < end; ++current) {
typename TSlot::TObject object = *current;
HeapObject heap_object;
if (object.GetHeapObjectIfStrong(&heap_object)) {
VerifyHeapObjectImpl(heap_object);
}
}
}
void VerifyPointers(ObjectSlot start, ObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VerifyPointers(MaybeObjectSlot start, MaybeObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
VerifyHeapObjectImpl(target);
}
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
VerifyHeapObjectImpl(rinfo->target_object());
}
void VerifyRootPointers(FullObjectSlot start, FullObjectSlot end) override {
VerifyPointersImpl(start, end);
}
};
} // namespace
#endif // VERIFY_HEAP
// =============================================================================
// MarkCompactCollectorBase, MinorMarkCompactCollector, MarkCompactCollector
// =============================================================================
namespace {
int NumberOfAvailableCores() {
static int num_cores = V8::GetCurrentPlatform()->NumberOfWorkerThreads() + 1;
// This number of cores should be greater than zero and never change.
DCHECK_GE(num_cores, 1);
DCHECK_EQ(num_cores, V8::GetCurrentPlatform()->NumberOfWorkerThreads() + 1);
return num_cores;
}
} // namespace
int MarkCompactCollectorBase::NumberOfParallelCompactionTasks() {
int tasks = FLAG_parallel_compaction ? NumberOfAvailableCores() : 1;
if (!heap_->CanPromoteYoungAndExpandOldGeneration(
static_cast<size_t>(tasks * Page::kPageSize))) {
// Optimize for memory usage near the heap limit.
tasks = 1;
}
return tasks;
}
MarkCompactCollector::MarkCompactCollector(Heap* heap)
: MarkCompactCollectorBase(heap),
page_parallel_job_semaphore_(0),
#ifdef DEBUG
state_(IDLE),
#endif
was_marked_incrementally_(false),
evacuation_(false),
compacting_(false),
black_allocation_(false),
have_code_to_deoptimize_(false),
sweeper_(new Sweeper(heap, non_atomic_marking_state())) {
old_to_new_slots_ = -1;
}
MarkCompactCollector::~MarkCompactCollector() { delete sweeper_; }
void MarkCompactCollector::SetUp() {
DCHECK_EQ(0, strcmp(Marking::kWhiteBitPattern, "00"));
DCHECK_EQ(0, strcmp(Marking::kBlackBitPattern, "11"));
DCHECK_EQ(0, strcmp(Marking::kGreyBitPattern, "10"));
DCHECK_EQ(0, strcmp(Marking::kImpossibleBitPattern, "01"));
}
void MarkCompactCollector::TearDown() {
AbortCompaction();
AbortWeakObjects();
if (heap()->incremental_marking()->IsMarking()) {
local_marking_worklists()->Publish();
heap()->marking_barrier()->Publish();
// Marking barriers of LocalHeaps will be published in their destructors.
marking_worklists()->Clear();
}
}
void MarkCompactCollector::AddEvacuationCandidate(Page* p) {
DCHECK(!p->NeverEvacuate());
if (FLAG_trace_evacuation_candidates) {
PrintIsolate(
isolate(),
"Evacuation candidate: Free bytes: %6zu. Free Lists length: %4d.\n",
p->area_size() - p->allocated_bytes(), p->FreeListsLength());
}
p->MarkEvacuationCandidate();
evacuation_candidates_.push_back(p);
}
static void TraceFragmentation(PagedSpace* space) {
int number_of_pages = space->CountTotalPages();
intptr_t reserved = (number_of_pages * space->AreaSize());
intptr_t free = reserved - space->SizeOfObjects();
PrintF("[%s]: %d pages, %d (%.1f%%) free\n", space->name(), number_of_pages,
static_cast<int>(free), static_cast<double>(free) * 100 / reserved);
}
bool MarkCompactCollector::StartCompaction() {
if (!compacting_) {
DCHECK(evacuation_candidates_.empty());
if (FLAG_gc_experiment_less_compaction && !heap_->ShouldReduceMemory())
return false;
CollectEvacuationCandidates(heap()->old_space());
if (FLAG_compact_code_space) {
CollectEvacuationCandidates(heap()->code_space());
} else if (FLAG_trace_fragmentation) {
TraceFragmentation(heap()->code_space());
}
if (FLAG_trace_fragmentation) {
TraceFragmentation(heap()->map_space());
}
compacting_ = !evacuation_candidates_.empty();
}
return compacting_;
}
void MarkCompactCollector::StartMarking() {
std::vector<Address> contexts =
heap()->memory_measurement()->StartProcessing();
if (FLAG_stress_per_context_marking_worklist) {
contexts.clear();
HandleScope handle_scope(heap()->isolate());
for (auto context : heap()->FindAllNativeContexts()) {
contexts.push_back(context->ptr());
}
}
marking_worklists()->CreateContextWorklists(contexts);
local_marking_worklists_ =
std::make_unique<MarkingWorklists::Local>(marking_worklists());
marking_visitor_ = std::make_unique<MarkingVisitor>(
marking_state(), local_marking_worklists(), weak_objects(), heap_,
epoch(), Heap::GetBytecodeFlushMode(),
heap_->local_embedder_heap_tracer()->InUse(),
heap_->is_current_gc_forced());
// Marking bits are cleared by the sweeper.
#ifdef VERIFY_HEAP
if (FLAG_verify_heap) {
VerifyMarkbitsAreClean();
}
#endif
}
void MarkCompactCollector::CollectGarbage() {
// Make sure that Prepare() has been called. The individual steps below will
// update the state as they proceed.
DCHECK(state_ == PREPARE_GC);
#ifdef ENABLE_MINOR_MC
heap()->minor_mark_compact_collector()->CleanupSweepToIteratePages();
#endif // ENABLE_MINOR_MC
MarkLiveObjects();
ClearNonLiveReferences();
VerifyMarking();
heap()->memory_measurement()->FinishProcessing(native_context_stats_);
RecordObjectStats();
StartSweepSpaces();
Evacuate();
Finish();
}
#ifdef VERIFY_HEAP
void MarkCompactCollector::VerifyMarkbitsAreDirty(ReadOnlySpace* space) {
ReadOnlyHeapObjectIterator iterator(space);
for (HeapObject object = iterator.Next(); !object.is_null();
object = iterator.Next()) {
CHECK(non_atomic_marking_state()->IsBlack(object));
}
}
void MarkCompactCollector::VerifyMarkbitsAreClean(PagedSpace* space) {
for (Page* p : *space) {
CHECK(non_atomic_marking_state()->bitmap(p)->IsClean());
CHECK_EQ(0, non_atomic_marking_state()->live_bytes(p));
}
}
void MarkCompactCollector::VerifyMarkbitsAreClean(NewSpace* space) {
for (Page* p : PageRange(space->first_allocatable_address(), space->top())) {
CHECK(non_atomic_marking_state()->bitmap(p)->IsClean());
CHECK_EQ(0, non_atomic_marking_state()->live_bytes(p));
}
}
void MarkCompactCollector::VerifyMarkbitsAreClean(LargeObjectSpace* space) {
LargeObjectSpaceObjectIterator it(space);
for (HeapObject obj = it.Next(); !obj.is_null(); obj = it.Next()) {
CHECK(non_atomic_marking_state()->IsWhite(obj));
CHECK_EQ(0, non_atomic_marking_state()->live_bytes(
MemoryChunk::FromHeapObject(obj)));
}
}
void MarkCompactCollector::VerifyMarkbitsAreClean() {
VerifyMarkbitsAreClean(heap_->old_space());
VerifyMarkbitsAreClean(heap_->code_space());
VerifyMarkbitsAreClean(heap_->map_space());
VerifyMarkbitsAreClean(heap_->new_space());
// Read-only space should always be black since we never collect any objects
// in it or linked from it.
VerifyMarkbitsAreDirty(heap_->read_only_space());
VerifyMarkbitsAreClean(heap_->lo_space());
VerifyMarkbitsAreClean(heap_->code_lo_space());
VerifyMarkbitsAreClean(heap_->new_lo_space());
}
#endif // VERIFY_HEAP
void MarkCompactCollector::EnsureSweepingCompleted() {
if (!sweeper()->sweeping_in_progress()) return;
sweeper()->EnsureCompleted();
heap()->old_space()->RefillFreeList();
heap()->code_space()->RefillFreeList();
heap()->map_space()->RefillFreeList();
heap()->map_space()->SortFreeList();
heap()->tracer()->NotifySweepingCompleted();
#ifdef VERIFY_HEAP
if (FLAG_verify_heap && !evacuation()) {
FullEvacuationVerifier verifier(heap());
verifier.Run();
}
#endif
}
void MarkCompactCollector::DrainSweepingWorklists() {
if (!sweeper()->sweeping_in_progress()) return;
sweeper()->DrainSweepingWorklists();
}
void MarkCompactCollector::DrainSweepingWorklistForSpace(
AllocationSpace space) {
if (!sweeper()->sweeping_in_progress()) return;
sweeper()->DrainSweepingWorklistForSpace(space);
}
void MarkCompactCollector::ComputeEvacuationHeuristics(
size_t area_size, int* target_fragmentation_percent,
size_t* max_evacuated_bytes) {
// For memory reducing and optimize for memory mode we directly define both
// constants.
const int kTargetFragmentationPercentForReduceMemory = 20;
const size_t kMaxEvacuatedBytesForReduceMemory = 12 * MB;
const int kTargetFragmentationPercentForOptimizeMemory = 20;
const size_t kMaxEvacuatedBytesForOptimizeMemory = 6 * MB;
// For regular mode (which is latency critical) we define less aggressive
// defaults to start and switch to a trace-based (using compaction speed)
// approach as soon as we have enough samples.
const int kTargetFragmentationPercent = 70;
const size_t kMaxEvacuatedBytes = 4 * MB;
// Time to take for a single area (=payload of page). Used as soon as there
// exist enough compaction speed samples.
const float kTargetMsPerArea = .5;
if (heap()->ShouldReduceMemory()) {
*target_fragmentation_percent = kTargetFragmentationPercentForReduceMemory;
*max_evacuated_bytes = kMaxEvacuatedBytesForReduceMemory;
} else if (heap()->ShouldOptimizeForMemoryUsage()) {
*target_fragmentation_percent =
kTargetFragmentationPercentForOptimizeMemory;
*max_evacuated_bytes = kMaxEvacuatedBytesForOptimizeMemory;
} else {
const double estimated_compaction_speed =
heap()->tracer()->CompactionSpeedInBytesPerMillisecond();
if (estimated_compaction_speed != 0) {
// Estimate the target fragmentation based on traced compaction speed
// and a goal for a single page.
const double estimated_ms_per_area =
1 + area_size / estimated_compaction_speed;
*target_fragmentation_percent = static_cast<int>(
100 - 100 * kTargetMsPerArea / estimated_ms_per_area);
if (*target_fragmentation_percent <
kTargetFragmentationPercentForReduceMemory) {
*target_fragmentation_percent =
kTargetFragmentationPercentForReduceMemory;
}
} else {
*target_fragmentation_percent = kTargetFragmentationPercent;
}
*max_evacuated_bytes = kMaxEvacuatedBytes;
}
}
void MarkCompactCollector::CollectEvacuationCandidates(PagedSpace* space) {
DCHECK(space->identity() == OLD_SPACE || space->identity() == CODE_SPACE);
int number_of_pages = space->CountTotalPages();
size_t area_size = space->AreaSize();
const bool in_standard_path =
!(FLAG_manual_evacuation_candidates_selection ||
FLAG_stress_compaction_random || FLAG_stress_compaction ||
FLAG_always_compact);
// Those variables will only be initialized if |in_standard_path|, and are not
// used otherwise.
size_t max_evacuated_bytes;
int target_fragmentation_percent;
size_t free_bytes_threshold;
if (in_standard_path) {
// We use two conditions to decide whether a page qualifies as an evacuation
// candidate, or not:
// * Target fragmentation: How fragmented is a page, i.e., how is the ratio
// between live bytes and capacity of this page (= area).
// * Evacuation quota: A global quota determining how much bytes should be
// compacted.
ComputeEvacuationHeuristics(area_size, &target_fragmentation_percent,
&max_evacuated_bytes);
free_bytes_threshold = target_fragmentation_percent * (area_size / 100);
}
// Pairs of (live_bytes_in_page, page).
using LiveBytesPagePair = std::pair<size_t, Page*>;
std::vector<LiveBytesPagePair> pages;
pages.reserve(number_of_pages);
DCHECK(!sweeping_in_progress());
Page* owner_of_linear_allocation_area =
space->top() == space->limit()
? nullptr
: Page::FromAllocationAreaAddress(space->top());
for (Page* p : *space) {
if (p->NeverEvacuate() || (p == owner_of_linear_allocation_area) ||
!p->CanAllocate())
continue;
if (p->IsPinned()) {
DCHECK(
!p->IsFlagSet(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING));
continue;
}
// Invariant: Evacuation candidates are just created when marking is
// started. This means that sweeping has finished. Furthermore, at the end
// of a GC all evacuation candidates are cleared and their slot buffers are
// released.
CHECK(!p->IsEvacuationCandidate());
CHECK_NULL(p->slot_set<OLD_TO_OLD>());
CHECK_NULL(p->typed_slot_set<OLD_TO_OLD>());
CHECK(p->SweepingDone());
DCHECK(p->area_size() == area_size);
if (in_standard_path) {
// Only the pages with at more than |free_bytes_threshold| free bytes are
// considered for evacuation.
if (area_size - p->allocated_bytes() >= free_bytes_threshold) {
pages.push_back(std::make_pair(p->allocated_bytes(), p));
}
} else {
pages.push_back(std::make_pair(p->allocated_bytes(), p));
}
// Unpin pages for the next GC
if (p->IsFlagSet(MemoryChunk::PINNED)) {
p->ClearFlag(MemoryChunk::PINNED);
}
}
int candidate_count = 0;
size_t total_live_bytes = 0;
const bool reduce_memory = heap()->ShouldReduceMemory();
if (FLAG_manual_evacuation_candidates_selection) {
for (size_t i = 0; i < pages.size(); i++) {
Page* p = pages[i].second;
if (p->IsFlagSet(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING)) {
candidate_count++;
total_live_bytes += pages[i].first;
p->ClearFlag(MemoryChunk::FORCE_EVACUATION_CANDIDATE_FOR_TESTING);
AddEvacuationCandidate(p);
}
}
} else if (FLAG_stress_compaction_random) {
double fraction = isolate()->fuzzer_rng()->NextDouble();
size_t pages_to_mark_count =
static_cast<size_t>(fraction * (pages.size() + 1));
for (uint64_t i : isolate()->fuzzer_rng()->NextSample(
pages.size(), pages_to_mark_count)) {
candidate_count++;
total_live_bytes += pages[i].first;
AddEvacuationCandidate(pages[i].second);
}
} else if (FLAG_stress_compaction) {
for (size_t i = 0; i < pages.size(); i++) {
Page* p = pages[i].second;
if (i % 2 == 0) {
candidate_count++;
total_live_bytes += pages[i].first;
AddEvacuationCandidate(p);
}
}
} else {
// The following approach determines the pages that should be evacuated.
//
// Sort pages from the most free to the least free, then select
// the first n pages for evacuation such that:
// - the total size of evacuated objects does not exceed the specified
// limit.
// - fragmentation of (n+1)-th page does not exceed the specified limit.
std::sort(pages.begin(), pages.end(),
[](const LiveBytesPagePair& a, const LiveBytesPagePair& b) {
return a.first < b.first;
});
for (size_t i = 0; i < pages.size(); i++) {
size_t live_bytes = pages[i].first;
DCHECK_GE(area_size, live_bytes);
if (FLAG_always_compact ||
((total_live_bytes + live_bytes) <= max_evacuated_bytes)) {
candidate_count++;
total_live_bytes += live_bytes;
}
if (FLAG_trace_fragmentation_verbose) {
PrintIsolate(isolate(),
"compaction-selection-page: space=%s free_bytes_page=%zu "
"fragmentation_limit_kb=%zu "
"fragmentation_limit_percent=%d sum_compaction_kb=%zu "
"compaction_limit_kb=%zu\n",
space->name(), (area_size - live_bytes) / KB,
free_bytes_threshold / KB, target_fragmentation_percent,
total_live_bytes / KB, max_evacuated_bytes / KB);
}
}
// How many pages we will allocated for the evacuated objects
// in the worst case: ceil(total_live_bytes / area_size)
int estimated_new_pages =
static_cast<int>((total_live_bytes + area_size - 1) / area_size);
DCHECK_LE(estimated_new_pages, candidate_count);
int estimated_released_pages = candidate_count - estimated_new_pages;
// Avoid (compact -> expand) cycles.
if ((estimated_released_pages == 0) && !FLAG_always_compact) {
candidate_count = 0;
}
for (int i = 0; i < candidate_count; i++) {
AddEvacuationCandidate(pages[i].second);
}
}
if (FLAG_trace_fragmentation) {
PrintIsolate(isolate(),
"compaction-selection: space=%s reduce_memory=%d pages=%d "
"total_live_bytes=%zu\n",
space->name(), reduce_memory, candidate_count,
total_live_bytes / KB);
}
}
void MarkCompactCollector::AbortCompaction() {
if (compacting_) {
RememberedSet<OLD_TO_OLD>::ClearAll(heap());
for (Page* p : evacuation_candidates_) {
p->ClearEvacuationCandidate();
}
compacting_ = false;
evacuation_candidates_.clear();
}
DCHECK(evacuation_candidates_.empty());
}
void MarkCompactCollector::Prepare() {
was_marked_incrementally_ = heap()->incremental_marking()->IsMarking();
#ifdef DEBUG
DCHECK(state_ == IDLE);
state_ = PREPARE_GC;
#endif
DCHECK(!FLAG_never_compact || !FLAG_always_compact);
// Instead of waiting we could also abort the sweeper threads here.
EnsureSweepingCompleted();
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_COMPLETE_SWEEP_ARRAY_BUFFERS);
heap_->array_buffer_sweeper()->EnsureFinished();
}
if (heap()->incremental_marking()->IsSweeping()) {
heap()->incremental_marking()->Stop();
}
if (!was_marked_incrementally_) {
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_EMBEDDER_PROLOGUE);
heap_->local_embedder_heap_tracer()->TracePrologue(
heap_->flags_for_embedder_tracer());
}
if (!FLAG_never_compact) {
StartCompaction();
}
StartMarking();
}
PagedSpaceIterator spaces(heap());
for (PagedSpace* space = spaces.Next(); space != nullptr;
space = spaces.Next()) {
space->PrepareForMarkCompact();
}
if (FLAG_local_heaps) {
// Fill and reset all background thread LABs
heap_->safepoint()->IterateLocalHeaps(
[](LocalHeap* local_heap) { local_heap->FreeLinearAllocationArea(); });
}
// All objects are guaranteed to be initialized in atomic pause
heap()->new_lo_space()->ResetPendingObject();
DCHECK_EQ(heap()->new_space()->top(),
heap()->new_space()->original_top_acquire());
}
void MarkCompactCollector::FinishConcurrentMarking() {
// FinishConcurrentMarking is called for both, concurrent and parallel,
// marking. It is safe to call this function when tasks are already finished.
if (FLAG_parallel_marking || FLAG_concurrent_marking) {
heap()->concurrent_marking()->Join();
heap()->concurrent_marking()->FlushMemoryChunkData(
non_atomic_marking_state());
heap()->concurrent_marking()->FlushNativeContexts(&native_context_stats_);
}
}
void MarkCompactCollector::VerifyMarking() {
CHECK(local_marking_worklists()->IsEmpty());
DCHECK(heap_->incremental_marking()->IsStopped());
#ifdef VERIFY_HEAP
if (FLAG_verify_heap) {
FullMarkingVerifier verifier(heap());
verifier.Run();
}
#endif
#ifdef VERIFY_HEAP
if (FLAG_verify_heap) {
heap()->old_space()->VerifyLiveBytes();
heap()->map_space()->VerifyLiveBytes();
heap()->code_space()->VerifyLiveBytes();
}
#endif
}
void MarkCompactCollector::Finish() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_FINISH);
SweepArrayBufferExtensions();
#ifdef DEBUG
heap()->VerifyCountersBeforeConcurrentSweeping();
#endif
marking_visitor_.reset();
local_marking_worklists_.reset();
marking_worklists_.ReleaseContextWorklists();
native_context_stats_.Clear();
CHECK(weak_objects_.current_ephemerons.IsEmpty());
CHECK(weak_objects_.discovered_ephemerons.IsEmpty());
weak_objects_.next_ephemerons.Clear();
sweeper()->StartSweeperTasks();
sweeper()->StartIterabilityTasks();
// Clear the marking state of live large objects.
heap_->lo_space()->ClearMarkingStateOfLiveObjects();
heap_->code_lo_space()->ClearMarkingStateOfLiveObjects();
#ifdef DEBUG
DCHECK(state_ == SWEEP_SPACES || state_ == RELOCATE_OBJECTS);
state_ = IDLE;
#endif
heap_->isolate()->inner_pointer_to_code_cache()->Flush();
// The stub caches are not traversed during GC; clear them to force
// their lazy re-initialization. This must be done after the
// GC, because it relies on the new address of certain old space
// objects (empty string, illegal builtin).
isolate()->load_stub_cache()->Clear();
isolate()->store_stub_cache()->Clear();
if (have_code_to_deoptimize_) {
// Some code objects were marked for deoptimization during the GC.
Deoptimizer::DeoptimizeMarkedCode(isolate());
have_code_to_deoptimize_ = false;
}
}
void MarkCompactCollector::SweepArrayBufferExtensions() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_FINISH_SWEEP_ARRAY_BUFFERS);
heap_->array_buffer_sweeper()->RequestSweepFull();
}
class MarkCompactCollector::RootMarkingVisitor final : public RootVisitor {
public:
explicit RootMarkingVisitor(MarkCompactCollector* collector)
: collector_(collector) {}
void VisitRootPointer(Root root, const char* description,
FullObjectSlot p) final {
MarkObjectByPointer(root, p);
}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) final {
for (FullObjectSlot p = start; p < end; ++p) MarkObjectByPointer(root, p);
}
private:
V8_INLINE void MarkObjectByPointer(Root root, FullObjectSlot p) {
if (!(*p).IsHeapObject()) return;
collector_->MarkRootObject(root, HeapObject::cast(*p));
}
MarkCompactCollector* const collector_;
};
// This visitor is used to visit the body of special objects held alive by
// other roots.
//
// It is currently used for
// - Code 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.
class MarkCompactCollector::CustomRootBodyMarkingVisitor final
: public ObjectVisitor {
public:
explicit CustomRootBodyMarkingVisitor(MarkCompactCollector* collector)
: collector_(collector) {}
void VisitPointer(HeapObject host, ObjectSlot p) final {
MarkObject(host, *p);
}
void VisitPointers(HeapObject host, ObjectSlot start, ObjectSlot end) final {
for (ObjectSlot p = start; p < end; ++p) {
DCHECK(!HasWeakHeapObjectTag(*p));
MarkObject(host, *p);
}
}
void VisitPointers(HeapObject host, MaybeObjectSlot start,
MaybeObjectSlot end) final {
// At the moment, custom roots cannot contain weak pointers.
UNREACHABLE();
}
// VisitEmbedderPointer is defined by ObjectVisitor to call VisitPointers.
void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
MarkObject(host, target);
}
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
MarkObject(host, rinfo->target_object());
}
private:
V8_INLINE void MarkObject(HeapObject host, Object object) {
if (!object.IsHeapObject()) return;
collector_->MarkObject(host, HeapObject::cast(object));
}
MarkCompactCollector* const collector_;
};
class InternalizedStringTableCleaner : public RootVisitor {
public:
explicit InternalizedStringTableCleaner(Heap* heap)
: heap_(heap), pointers_removed_(0) {}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) override {
UNREACHABLE();
}
void VisitRootPointers(Root root, const char* description,
OffHeapObjectSlot start,
OffHeapObjectSlot end) override {
DCHECK_EQ(root, Root::kStringTable);
// Visit all HeapObject pointers in [start, end).
MarkCompactCollector::NonAtomicMarkingState* marking_state =
heap_->mark_compact_collector()->non_atomic_marking_state();
Isolate* isolate = heap_->isolate();
for (OffHeapObjectSlot p = start; p < end; ++p) {
Object o = p.load(isolate);
if (o.IsHeapObject()) {
HeapObject heap_object = HeapObject::cast(o);
DCHECK(!Heap::InYoungGeneration(heap_object));
if (marking_state->IsWhite(heap_object)) {
pointers_removed_++;
// Set the entry to the_hole_value (as deleted).
p.store(StringTable::deleted_element());
}
}
}
}
int PointersRemoved() { return pointers_removed_; }
private:
Heap* heap_;
int pointers_removed_;
};
class ExternalStringTableCleaner : public RootVisitor {
public:
explicit ExternalStringTableCleaner(Heap* heap) : heap_(heap) {}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) override {
// Visit all HeapObject pointers in [start, end).
MarkCompactCollector::NonAtomicMarkingState* marking_state =
heap_->mark_compact_collector()->non_atomic_marking_state();
Object the_hole = ReadOnlyRoots(heap_).the_hole_value();
for (FullObjectSlot p = start; p < end; ++p) {
Object o = *p;
if (o.IsHeapObject()) {
HeapObject heap_object = HeapObject::cast(o);
if (marking_state->IsWhite(heap_object)) {
if (o.IsExternalString()) {
heap_->FinalizeExternalString(String::cast(o));
} else {
// The original external string may have been internalized.
DCHECK(o.IsThinString());
}
// Set the entry to the_hole_value (as deleted).
p.store(the_hole);
}
}
}
}
private:
Heap* heap_;
};
// Implementation of WeakObjectRetainer for mark compact GCs. All marked objects
// are retained.
class MarkCompactWeakObjectRetainer : public WeakObjectRetainer {
public:
explicit MarkCompactWeakObjectRetainer(
MarkCompactCollector::NonAtomicMarkingState* marking_state)
: marking_state_(marking_state) {}
Object RetainAs(Object object) override {
HeapObject heap_object = HeapObject::cast(object);
DCHECK(!marking_state_->IsGrey(heap_object));
if (marking_state_->IsBlack(heap_object)) {
return object;
} else if (object.IsAllocationSite() &&
!(AllocationSite::cast(object).IsZombie())) {
// "dead" AllocationSites need to live long enough for a traversal of new
// space. These sites get a one-time reprieve.
Object nested = object;
while (nested.IsAllocationSite()) {
AllocationSite current_site = AllocationSite::cast(nested);
// MarkZombie will override the nested_site, read it first before
// marking
nested = current_site.nested_site();
current_site.MarkZombie();
marking_state_->WhiteToBlack(current_site);
}
return object;
} else {
return Object();
}
}
private:
MarkCompactCollector::NonAtomicMarkingState* marking_state_;
};
class RecordMigratedSlotVisitor : public ObjectVisitor {
public:
explicit RecordMigratedSlotVisitor(
MarkCompactCollector* collector,
EphemeronRememberedSet* ephemeron_remembered_set)
: collector_(collector),
ephemeron_remembered_set_(ephemeron_remembered_set) {}
inline void VisitPointer(HeapObject host, ObjectSlot p) final {
DCHECK(!HasWeakHeapObjectTag(*p));
RecordMigratedSlot(host, MaybeObject::FromObject(*p), p.address());
}
inline void VisitPointer(HeapObject host, MaybeObjectSlot p) final {
RecordMigratedSlot(host, *p, p.address());
}
inline void VisitPointers(HeapObject host, ObjectSlot start,
ObjectSlot end) final {
while (start < end) {
VisitPointer(host, start);
++start;
}
}
inline void VisitPointers(HeapObject host, MaybeObjectSlot start,
MaybeObjectSlot end) final {
while (start < end) {
VisitPointer(host, start);
++start;
}
}
inline void VisitEphemeron(HeapObject host, int index, ObjectSlot key,
ObjectSlot value) override {
DCHECK(host.IsEphemeronHashTable());
DCHECK(!Heap::InYoungGeneration(host));
VisitPointer(host, value);
if (ephemeron_remembered_set_ && Heap::InYoungGeneration(*key)) {
auto table = EphemeronHashTable::unchecked_cast(host);
auto insert_result =
ephemeron_remembered_set_->insert({table, std::unordered_set<int>()});
insert_result.first->second.insert(index);
} else {
VisitPointer(host, key);
}
}
inline void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
DCHECK_EQ(host, rinfo->host());
DCHECK(RelocInfo::IsCodeTargetMode(rinfo->rmode()));
Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
// The target is always in old space, we don't have to record the slot in
// the old-to-new remembered set.
DCHECK(!Heap::InYoungGeneration(target));
collector_->RecordRelocSlot(host, rinfo, target);
}
inline void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
DCHECK_EQ(host, rinfo->host());
DCHECK(RelocInfo::IsEmbeddedObjectMode(rinfo->rmode()));
HeapObject object = HeapObject::cast(rinfo->target_object());
GenerationalBarrierForCode(host, rinfo, object);
collector_->RecordRelocSlot(host, rinfo, object);
}
// Entries that are skipped for recording.
inline void VisitExternalReference(Code host, RelocInfo* rinfo) final {}
inline void VisitExternalReference(Foreign host, Address* p) final {}
inline void VisitRuntimeEntry(Code host, RelocInfo* rinfo) final {}
inline void VisitInternalReference(Code host, RelocInfo* rinfo) final {}
virtual void MarkArrayBufferExtensionPromoted(HeapObject object) {}
protected:
inline virtual void RecordMigratedSlot(HeapObject host, MaybeObject value,
Address slot) {
if (value->IsStrongOrWeak()) {
BasicMemoryChunk* p = BasicMemoryChunk::FromAddress(value.ptr());
if (p->InYoungGeneration()) {
DCHECK_IMPLIES(
p->IsToPage(),
p->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION) || p->IsLargePage());
MemoryChunk* chunk = MemoryChunk::FromHeapObject(host);
DCHECK(chunk->SweepingDone());
DCHECK_NULL(chunk->sweeping_slot_set<AccessMode::NON_ATOMIC>());
RememberedSet<OLD_TO_NEW>::Insert<AccessMode::NON_ATOMIC>(chunk, slot);
} else if (p->IsEvacuationCandidate()) {
RememberedSet<OLD_TO_OLD>::Insert<AccessMode::NON_ATOMIC>(
MemoryChunk::FromHeapObject(host), slot);
}
}
}
MarkCompactCollector* collector_;
EphemeronRememberedSet* ephemeron_remembered_set_;
};
class MigrationObserver {
public:
explicit MigrationObserver(Heap* heap) : heap_(heap) {}
virtual ~MigrationObserver() = default;
virtual void Move(AllocationSpace dest, HeapObject src, HeapObject dst,
int size) = 0;
protected:
Heap* heap_;
};
class ProfilingMigrationObserver final : public MigrationObserver {
public:
explicit ProfilingMigrationObserver(Heap* heap) : MigrationObserver(heap) {}
inline void Move(AllocationSpace dest, HeapObject src, HeapObject dst,
int size) final {
if (dest == CODE_SPACE || (dest == OLD_SPACE && dst.IsBytecodeArray())) {
PROFILE(heap_->isolate(),
CodeMoveEvent(AbstractCode::cast(src), AbstractCode::cast(dst)));
}
heap_->OnMoveEvent(dst, src, size);
}
};
class HeapObjectVisitor {
public:
virtual ~HeapObjectVisitor() = default;
virtual bool Visit(HeapObject object, int size) = 0;
};
class EvacuateVisitorBase : public HeapObjectVisitor {
public:
void AddObserver(MigrationObserver* observer) {
migration_function_ = RawMigrateObject<MigrationMode::kObserved>;
observers_.push_back(observer);
}
protected:
enum MigrationMode { kFast, kObserved };
using MigrateFunction = void (*)(EvacuateVisitorBase* base, HeapObject dst,
HeapObject src, int size,
AllocationSpace dest);
template <MigrationMode mode>
static void RawMigrateObject(EvacuateVisitorBase* base, HeapObject dst,
HeapObject src, int size, AllocationSpace dest) {
Address dst_addr = dst.address();
Address src_addr = src.address();
DCHECK(base->heap_->AllowedToBeMigrated(src.map(), src, dest));
DCHECK_NE(dest, LO_SPACE);
DCHECK_NE(dest, CODE_LO_SPACE);
if (dest == OLD_SPACE) {
DCHECK_OBJECT_SIZE(size);
DCHECK(IsAligned(size, kTaggedSize));
base->heap_->CopyBlock(dst_addr, src_addr, size);
if (mode != MigrationMode::kFast)
base->ExecuteMigrationObservers(dest, src, dst, size);
dst.IterateBodyFast(dst.map(), size, base->record_visitor_);
if (V8_UNLIKELY(FLAG_minor_mc)) {
base->record_visitor_->MarkArrayBufferExtensionPromoted(dst);
}
} else if (dest == CODE_SPACE) {
DCHECK_CODEOBJECT_SIZE(size, base->heap_->code_space());
base->heap_->CopyBlock(dst_addr, src_addr, size);
Code::cast(dst).Relocate(dst_addr - src_addr);
if (mode != MigrationMode::kFast)
base->ExecuteMigrationObservers(dest, src, dst, size);
dst.IterateBodyFast(dst.map(), size, base->record_visitor_);
} else {
DCHECK_OBJECT_SIZE(size);
DCHECK(dest == NEW_SPACE);
base->heap_->CopyBlock(dst_addr, src_addr, size);
if (mode != MigrationMode::kFast)
base->ExecuteMigrationObservers(dest, src, dst, size);
}
src.set_map_word(MapWord::FromForwardingAddress(dst));
}
EvacuateVisitorBase(Heap* heap, EvacuationAllocator* local_allocator,
RecordMigratedSlotVisitor* record_visitor)
: heap_(heap),
local_allocator_(local_allocator),
record_visitor_(record_visitor) {
migration_function_ = RawMigrateObject<MigrationMode::kFast>;
}
inline bool TryEvacuateObject(AllocationSpace target_space, HeapObject object,
int size, HeapObject* target_object) {
#ifdef VERIFY_HEAP
if (FLAG_verify_heap && AbortCompactionForTesting(object)) return false;
#endif // VERIFY_HEAP
AllocationAlignment alignment = HeapObject::RequiredAlignment(object.map());
AllocationResult allocation = local_allocator_->Allocate(
target_space, size, AllocationOrigin::kGC, alignment);
if (allocation.To(target_object)) {
MigrateObject(*target_object, object, size, target_space);
if (target_space == CODE_SPACE)
MemoryChunk::FromHeapObject(*target_object)
->GetCodeObjectRegistry()
->RegisterNewlyAllocatedCodeObject((*target_object).address());
return true;
}
return false;
}
inline void ExecuteMigrationObservers(AllocationSpace dest, HeapObject src,
HeapObject dst, int size) {
for (MigrationObserver* obs : observers_) {
obs->Move(dest, src, dst, size);
}
}
inline void MigrateObject(HeapObject dst, HeapObject src, int size,
AllocationSpace dest) {
migration_function_(this, dst, src, size, dest);
}
#ifdef VERIFY_HEAP
bool AbortCompactionForTesting(HeapObject object) {
if (FLAG_stress_compaction) {
const uintptr_t mask = static_cast<uintptr_t>(FLAG_random_seed) &
kPageAlignmentMask & ~kObjectAlignmentMask;
if ((object.ptr() & kPageAlignmentMask) == mask) {
Page* page = Page::FromHeapObject(object);
if (page->IsFlagSet(Page::COMPACTION_WAS_ABORTED_FOR_TESTING)) {
page->ClearFlag(Page::COMPACTION_WAS_ABORTED_FOR_TESTING);
} else {
page->SetFlag(Page::COMPACTION_WAS_ABORTED_FOR_TESTING);
return true;
}
}
}
return false;
}
#endif // VERIFY_HEAP
Heap* heap_;
EvacuationAllocator* local_allocator_;
RecordMigratedSlotVisitor* record_visitor_;
std::vector<MigrationObserver*> observers_;
MigrateFunction migration_function_;
};
class EvacuateNewSpaceVisitor final : public EvacuateVisitorBase {
public:
explicit EvacuateNewSpaceVisitor(
Heap* heap, EvacuationAllocator* local_allocator,
RecordMigratedSlotVisitor* record_visitor,
Heap::PretenuringFeedbackMap* local_pretenuring_feedback,
bool always_promote_young)
: EvacuateVisitorBase(heap, local_allocator, record_visitor),
buffer_(LocalAllocationBuffer::InvalidBuffer()),
promoted_size_(0),
semispace_copied_size_(0),
local_pretenuring_feedback_(local_pretenuring_feedback),
is_incremental_marking_(heap->incremental_marking()->IsMarking()),
always_promote_young_(always_promote_young) {}
inline bool Visit(HeapObject object, int size) override {
if (TryEvacuateWithoutCopy(object)) return true;
HeapObject target_object;
if (always_promote_young_) {
heap_->UpdateAllocationSite(object.map(), object,
local_pretenuring_feedback_);
if (!TryEvacuateObject(OLD_SPACE, object, size, &target_object)) {
heap_->FatalProcessOutOfMemory(
"MarkCompactCollector: young object promotion failed");
}
promoted_size_ += size;
return true;
}
if (heap_->ShouldBePromoted(object.address()) &&
TryEvacuateObject(OLD_SPACE, object, size, &target_object)) {
promoted_size_ += size;
return true;
}
heap_->UpdateAllocationSite(object.map(), object,
local_pretenuring_feedback_);
HeapObject target;
AllocationSpace space = AllocateTargetObject(object, size, &target);
MigrateObject(HeapObject::cast(target), object, size, space);
semispace_copied_size_ += size;
return true;
}
intptr_t promoted_size() { return promoted_size_; }
intptr_t semispace_copied_size() { return semispace_copied_size_; }
private:
inline bool TryEvacuateWithoutCopy(HeapObject object) {
if (is_incremental_marking_) return false;
Map map = object.map();
// Some objects can be evacuated without creating a copy.
if (map.visitor_id() == kVisitThinString) {
HeapObject actual = ThinString::cast(object).unchecked_actual();
if (MarkCompactCollector::IsOnEvacuationCandidate(actual)) return false;
object.set_map_word(MapWord::FromForwardingAddress(actual));
return true;
}
// TODO(mlippautz): Handle ConsString.
return false;
}
inline AllocationSpace AllocateTargetObject(HeapObject old_object, int size,
HeapObject* target_object) {
AllocationAlignment alignment =
HeapObject::RequiredAlignment(old_object.map());
AllocationSpace space_allocated_in = NEW_SPACE;
AllocationResult allocation = local_allocator_->Allocate(
NEW_SPACE, size, AllocationOrigin::kGC, alignment);
if (allocation.IsRetry()) {
allocation = AllocateInOldSpace(size, alignment);
space_allocated_in = OLD_SPACE;
}
bool ok = allocation.To(target_object);
DCHECK(ok);
USE(ok);
return space_allocated_in;
}
inline AllocationResult AllocateInOldSpace(int size_in_bytes,
AllocationAlignment alignment) {
AllocationResult allocation = local_allocator_->Allocate(
OLD_SPACE, size_in_bytes, AllocationOrigin::kGC, alignment);
if (allocation.IsRetry()) {
heap_->FatalProcessOutOfMemory(
"MarkCompactCollector: semi-space copy, fallback in old gen");
}
return allocation;
}
LocalAllocationBuffer buffer_;
intptr_t promoted_size_;
intptr_t semispace_copied_size_;
Heap::PretenuringFeedbackMap* local_pretenuring_feedback_;
bool is_incremental_marking_;
bool always_promote_young_;
};
template <PageEvacuationMode mode>
class EvacuateNewSpacePageVisitor final : public HeapObjectVisitor {
public:
explicit EvacuateNewSpacePageVisitor(
Heap* heap, RecordMigratedSlotVisitor* record_visitor,
Heap::PretenuringFeedbackMap* local_pretenuring_feedback)
: heap_(heap),
record_visitor_(record_visitor),
moved_bytes_(0),
local_pretenuring_feedback_(local_pretenuring_feedback) {}
static void Move(Page* page) {
switch (mode) {
case NEW_TO_NEW:
page->heap()->new_space()->MovePageFromSpaceToSpace(page);
page->SetFlag(Page::PAGE_NEW_NEW_PROMOTION);
break;
case NEW_TO_OLD: {
page->heap()->new_space()->from_space().RemovePage(page);
Page* new_page = Page::ConvertNewToOld(page);
DCHECK(!new_page->InYoungGeneration());
new_page->SetFlag(Page::PAGE_NEW_OLD_PROMOTION);
break;
}
}
}
inline bool Visit(HeapObject object, int size) override {
if (mode == NEW_TO_NEW) {
heap_->UpdateAllocationSite(object.map(), object,
local_pretenuring_feedback_);
} else if (mode == NEW_TO_OLD) {
object.IterateBodyFast(record_visitor_);
if (V8_UNLIKELY(FLAG_minor_mc)) {
record_visitor_->MarkArrayBufferExtensionPromoted(object);
}
}
return true;
}
intptr_t moved_bytes() { return moved_bytes_; }
void account_moved_bytes(intptr_t bytes) { moved_bytes_ += bytes; }
private:
Heap* heap_;
RecordMigratedSlotVisitor* record_visitor_;
intptr_t moved_bytes_;
Heap::PretenuringFeedbackMap* local_pretenuring_feedback_;
};
class EvacuateOldSpaceVisitor final : public EvacuateVisitorBase {
public:
EvacuateOldSpaceVisitor(Heap* heap, EvacuationAllocator* local_allocator,
RecordMigratedSlotVisitor* record_visitor)
: EvacuateVisitorBase(heap, local_allocator, record_visitor) {}
inline bool Visit(HeapObject object, int size) override {
HeapObject target_object;
if (TryEvacuateObject(Page::FromHeapObject(object)->owner_identity(),
object, size, &target_object)) {
DCHECK(object.map_word().IsForwardingAddress());
return true;
}
return false;
}
};
class EvacuateRecordOnlyVisitor final : public HeapObjectVisitor {
public:
explicit EvacuateRecordOnlyVisitor(Heap* heap) : heap_(heap) {}
inline bool Visit(HeapObject object, int size) override {
RecordMigratedSlotVisitor visitor(heap_->mark_compact_collector(),
&heap_->ephemeron_remembered_set_);
object.IterateBodyFast(&visitor);
return true;
}
private:
Heap* heap_;
};
bool MarkCompactCollector::IsUnmarkedHeapObject(Heap* heap, FullObjectSlot p) {
Object o = *p;
if (!o.IsHeapObject()) return false;
HeapObject heap_object = HeapObject::cast(o);
return heap->mark_compact_collector()->non_atomic_marking_state()->IsWhite(
heap_object);
}
void MarkCompactCollector::MarkRoots(RootVisitor* root_visitor,
ObjectVisitor* custom_root_body_visitor) {
// Mark the heap roots including global variables, stack variables,
// etc., and all objects reachable from them.
heap()->IterateRoots(root_visitor, base::EnumSet<SkipRoot>{SkipRoot::kWeak});
// Custom marking for top optimized frame.
ProcessTopOptimizedFrame(custom_root_body_visitor);
}
void MarkCompactCollector::VisitObject(HeapObject obj) {
marking_visitor_->Visit(obj.map(), obj);
}
void MarkCompactCollector::RevisitObject(HeapObject obj) {
DCHECK(marking_state()->IsBlack(obj));
DCHECK_IMPLIES(MemoryChunk::FromHeapObject(obj)->IsFlagSet(
MemoryChunk::HAS_PROGRESS_BAR),
0u == MemoryChunk::FromHeapObject(obj)->ProgressBar());
MarkingVisitor::RevisitScope revisit(marking_visitor_.get());
marking_visitor_->Visit(obj.map(), obj);
}
void MarkCompactCollector::MarkDescriptorArrayFromWriteBarrier(
DescriptorArray descriptors, int number_of_own_descriptors) {
marking_visitor_->MarkDescriptorArrayFromWriteBarrier(
descriptors, number_of_own_descriptors);
}
void MarkCompactCollector::ProcessEphemeronsUntilFixpoint() {
bool work_to_do = true;
int iterations = 0;
int max_iterations = FLAG_ephemeron_fixpoint_iterations;
while (work_to_do) {
PerformWrapperTracing();
if (iterations >= max_iterations) {
// Give up fixpoint iteration and switch to linear algorithm.
ProcessEphemeronsLinear();
break;
}
// Move ephemerons from next_ephemerons into current_ephemerons to
// drain them in this iteration.
weak_objects_.current_ephemerons.Swap(weak_objects_.next_ephemerons);
heap()->concurrent_marking()->set_ephemeron_marked(false);
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_WEAK_CLOSURE_EPHEMERON_MARKING);
if (FLAG_parallel_marking) {
heap_->concurrent_marking()->RescheduleJobIfNeeded(
TaskPriority::kUserBlocking);
}
work_to_do = ProcessEphemerons();
FinishConcurrentMarking();
}
CHECK(weak_objects_.current_ephemerons.IsEmpty());
CHECK(weak_objects_.discovered_ephemerons.IsEmpty());
work_to_do = work_to_do || !local_marking_worklists()->IsEmpty() ||
heap()->concurrent_marking()->ephemeron_marked() ||
!local_marking_worklists()->IsEmbedderEmpty() ||
!heap()->local_embedder_heap_tracer()->IsRemoteTracingDone();
++iterations;
}
CHECK(local_marking_worklists()->IsEmpty());
CHECK(weak_objects_.current_ephemerons.IsEmpty());
CHECK(weak_objects_.discovered_ephemerons.IsEmpty());
}
bool MarkCompactCollector::ProcessEphemerons() {
Ephemeron ephemeron;
bool ephemeron_marked = false;
// Drain current_ephemerons and push ephemerons where key and value are still
// unreachable into next_ephemerons.
while (weak_objects_.current_ephemerons.Pop(kMainThreadTask, &ephemeron)) {
if (ProcessEphemeron(ephemeron.key, ephemeron.value)) {
ephemeron_marked = true;
}
}
// Drain marking worklist and push discovered ephemerons into
// discovered_ephemerons.
DrainMarkingWorklist();
// Drain discovered_ephemerons (filled in the drain MarkingWorklist-phase
// before) and push ephemerons where key and value are still unreachable into
// next_ephemerons.
while (weak_objects_.discovered_ephemerons.Pop(kMainThreadTask, &ephemeron)) {
if (ProcessEphemeron(ephemeron.key, ephemeron.value)) {
ephemeron_marked = true;
}
}
// Flush local ephemerons for main task to global pool.
weak_objects_.ephemeron_hash_tables.FlushToGlobal(kMainThreadTask);
weak_objects_.next_ephemerons.FlushToGlobal(kMainThreadTask);
return ephemeron_marked;
}
void MarkCompactCollector::ProcessEphemeronsLinear() {
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_WEAK_CLOSURE_EPHEMERON_LINEAR);
CHECK(heap()->concurrent_marking()->IsStopped());
std::unordered_multimap<HeapObject, HeapObject, Object::Hasher> key_to_values;
Ephemeron ephemeron;
DCHECK(weak_objects_.current_ephemerons.IsEmpty());
weak_objects_.current_ephemerons.Swap(weak_objects_.next_ephemerons);
while (weak_objects_.current_ephemerons.Pop(kMainThreadTask, &ephemeron)) {
ProcessEphemeron(ephemeron.key, ephemeron.value);
if (non_atomic_marking_state()->IsWhite(ephemeron.value)) {
key_to_values.insert(std::make_pair(ephemeron.key, ephemeron.value));
}
}
ephemeron_marking_.newly_discovered_limit = key_to_values.size();
bool work_to_do = true;
while (work_to_do) {
PerformWrapperTracing();
ResetNewlyDiscovered();
ephemeron_marking_.newly_discovered_limit = key_to_values.size();
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_WEAK_CLOSURE_EPHEMERON_MARKING);
// Drain marking worklist and push all discovered objects into
// newly_discovered.
ProcessMarkingWorklist<
MarkCompactCollector::MarkingWorklistProcessingMode::
kTrackNewlyDiscoveredObjects>(0);
}
while (
weak_objects_.discovered_ephemerons.Pop(kMainThreadTask, &ephemeron)) {
ProcessEphemeron(ephemeron.key, ephemeron.value);
if (non_atomic_marking_state()->IsWhite(ephemeron.value)) {
key_to_values.insert(std::make_pair(ephemeron.key, ephemeron.value));
}
}
if (ephemeron_marking_.newly_discovered_overflowed) {
// If newly_discovered was overflowed just visit all ephemerons in
// next_ephemerons.
weak_objects_.next_ephemerons.Iterate([&](Ephemeron ephemeron) {
if (non_atomic_marking_state()->IsBlackOrGrey(ephemeron.key) &&
non_atomic_marking_state()->WhiteToGrey(ephemeron.value)) {
local_marking_worklists()->Push(ephemeron.value);
}
});
} else {
// This is the good case: newly_discovered stores all discovered
// objects. Now use key_to_values to see if discovered objects keep more
// objects alive due to ephemeron semantics.
for (HeapObject object : ephemeron_marking_.newly_discovered) {
auto range = key_to_values.equal_range(object);
for (auto it = range.first; it != range.second; ++it) {
HeapObject value = it->second;
MarkObject(object, value);
}
}
}
// Do NOT drain marking worklist here, otherwise the current checks
// for work_to_do are not sufficient for determining if another iteration
// is necessary.
work_to_do = !local_marking_worklists()->IsEmpty() ||
!local_marking_worklists()->IsEmbedderEmpty() ||
!heap()->local_embedder_heap_tracer()->IsRemoteTracingDone();
CHECK(weak_objects_.discovered_ephemerons.IsEmpty());
}
ResetNewlyDiscovered();
ephemeron_marking_.newly_discovered.shrink_to_fit();
CHECK(local_marking_worklists()->IsEmpty());
}
void MarkCompactCollector::PerformWrapperTracing() {
if (heap_->local_embedder_heap_tracer()->InUse()) {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_EMBEDDER_TRACING);
{
LocalEmbedderHeapTracer::ProcessingScope scope(
heap_->local_embedder_heap_tracer());
HeapObject object;
while (local_marking_worklists()->PopEmbedder(&object)) {
scope.TracePossibleWrapper(JSObject::cast(object));
}
}
heap_->local_embedder_heap_tracer()->Trace(
std::numeric_limits<double>::infinity());
}
}
void MarkCompactCollector::DrainMarkingWorklist() { ProcessMarkingWorklist(0); }
template <MarkCompactCollector::MarkingWorklistProcessingMode mode>
size_t MarkCompactCollector::ProcessMarkingWorklist(size_t bytes_to_process) {
HeapObject object;
size_t bytes_processed = 0;
bool is_per_context_mode = local_marking_worklists()->IsPerContextMode();
Isolate* isolate = heap()->isolate();
while (local_marking_worklists()->Pop(&object) ||
local_marking_worklists()->PopOnHold(&object)) {
// Left trimming may result in grey or black filler objects on the marking
// worklist. Ignore these objects.
if (object.IsFreeSpaceOrFiller()) {
// Due to copying mark bits and the fact that grey and black have their
// first bit set, one word fillers are always black.
DCHECK_IMPLIES(
object.map() == ReadOnlyRoots(heap()).one_pointer_filler_map(),
marking_state()->IsBlack(object));
// Other fillers may be black or grey depending on the color of the object
// that was trimmed.
DCHECK_IMPLIES(
object.map() != ReadOnlyRoots(heap()).one_pointer_filler_map(),
marking_state()->IsBlackOrGrey(object));
continue;
}
DCHECK(object.IsHeapObject());
DCHECK(heap()->Contains(object));
DCHECK(!(marking_state()->IsWhite(object)));
if (mode == MarkCompactCollector::MarkingWorklistProcessingMode::
kTrackNewlyDiscoveredObjects) {
AddNewlyDiscovered(object);
}
Map map = object.map(isolate);
if (is_per_context_mode) {
Address context;
if (native_context_inferrer_.Infer(isolate, map, object, &context)) {
local_marking_worklists()->SwitchToContext(context);
}
}
size_t visited_size = marking_visitor_->Visit(map, object);
if (is_per_context_mode) {
native_context_stats_.IncrementSize(local_marking_worklists()->Context(),
map, object, visited_size);
}
bytes_processed += visited_size;
if (bytes_to_process && bytes_processed >= bytes_to_process) {
break;
}
}
return bytes_processed;
}
// Generate definitions for use in other files.
template size_t MarkCompactCollector::ProcessMarkingWorklist<
MarkCompactCollector::MarkingWorklistProcessingMode::kDefault>(
size_t bytes_to_process);
template size_t MarkCompactCollector::ProcessMarkingWorklist<
MarkCompactCollector::MarkingWorklistProcessingMode::
kTrackNewlyDiscoveredObjects>(size_t bytes_to_process);
bool MarkCompactCollector::ProcessEphemeron(HeapObject key, HeapObject value) {
if (marking_state()->IsBlackOrGrey(key)) {
if (marking_state()->WhiteToGrey(value)) {
local_marking_worklists()->Push(value);
return true;
}
} else if (marking_state()->IsWhite(value)) {
weak_objects_.next_ephemerons.Push(kMainThreadTask, Ephemeron{key, value});
}
return false;
}
void MarkCompactCollector::ProcessEphemeronMarking() {
DCHECK(local_marking_worklists()->IsEmpty());
// Incremental marking might leave ephemerons in main task's local
// buffer, flush it into global pool.
weak_objects_.next_ephemerons.FlushToGlobal(kMainThreadTask);
ProcessEphemeronsUntilFixpoint();
CHECK(local_marking_worklists()->IsEmpty());
CHECK(heap()->local_embedder_heap_tracer()->IsRemoteTracingDone());
}
void MarkCompactCollector::ProcessTopOptimizedFrame(ObjectVisitor* visitor) {
for (StackFrameIterator it(isolate(), isolate()->thread_local_top());
!it.done(); it.Advance()) {
if (it.frame()->type() == StackFrame::INTERPRETED) {
return;
}
if (it.frame()->type() == StackFrame::OPTIMIZED) {
Code code = it.frame()->LookupCode();
if (!code.CanDeoptAt(it.frame()->pc())) {
Code::BodyDescriptor::IterateBody(code.map(), code, visitor);
}
return;
}
}
}
void MarkCompactCollector::RecordObjectStats() {
if (V8_UNLIKELY(TracingFlags::is_gc_stats_enabled())) {
heap()->CreateObjectStats();
ObjectStatsCollector collector(heap(), heap()->live_object_stats_.get(),
heap()->dead_object_stats_.get());
collector.Collect();
if (V8_UNLIKELY(TracingFlags::gc_stats.load(std::memory_order_relaxed) &
v8::tracing::TracingCategoryObserver::ENABLED_BY_TRACING)) {
std::stringstream live, dead;
heap()->live_object_stats_->Dump(live);
heap()->dead_object_stats_->Dump(dead);
TRACE_EVENT_INSTANT2(TRACE_DISABLED_BY_DEFAULT("v8.gc_stats"),
"V8.GC_Objects_Stats", TRACE_EVENT_SCOPE_THREAD,
"live", TRACE_STR_COPY(live.str().c_str()), "dead",
TRACE_STR_COPY(dead.str().c_str()));
}
if (FLAG_trace_gc_object_stats) {
heap()->live_object_stats_->PrintJSON("live");
heap()->dead_object_stats_->PrintJSON("dead");
}
heap()->live_object_stats_->CheckpointObjectStats();
heap()->dead_object_stats_->ClearObjectStats();
}
}
void MarkCompactCollector::MarkLiveObjects() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK);
// The recursive GC marker detects when it is nearing stack overflow,
// and switches to a different marking system. JS interrupts interfere
// with the C stack limit check.
PostponeInterruptsScope postpone(isolate());
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_FINISH_INCREMENTAL);
IncrementalMarking* incremental_marking = heap_->incremental_marking();
if (was_marked_incrementally_) {
incremental_marking->Finalize();
MarkingBarrier::PublishAll(heap());
} else {
CHECK(incremental_marking->IsStopped());
}
}
#ifdef DEBUG
DCHECK(state_ == PREPARE_GC);
state_ = MARK_LIVE_OBJECTS;
#endif
heap_->local_embedder_heap_tracer()->EnterFinalPause();
RootMarkingVisitor root_visitor(this);
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_ROOTS);
CustomRootBodyMarkingVisitor custom_root_body_visitor(this);
MarkRoots(&root_visitor, &custom_root_body_visitor);
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_MAIN);
if (FLAG_parallel_marking) {
heap_->concurrent_marking()->RescheduleJobIfNeeded(
TaskPriority::kUserBlocking);
}
DrainMarkingWorklist();
FinishConcurrentMarking();
DrainMarkingWorklist();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_WEAK_CLOSURE);
DCHECK(local_marking_worklists()->IsEmpty());
// Mark objects reachable through the embedder heap. This phase is
// opportunistic as it may not discover graphs that are only reachable
// through ephemerons.
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_EMBEDDER_TRACING_CLOSURE);
do {
// PerformWrapperTracing() also empties the work items collected by
// concurrent markers. As a result this call needs to happen at least
// once.
PerformWrapperTracing();
DrainMarkingWorklist();
} while (!heap_->local_embedder_heap_tracer()->IsRemoteTracingDone() ||
!local_marking_worklists()->IsEmbedderEmpty());
DCHECK(local_marking_worklists()->IsEmbedderEmpty());
DCHECK(local_marking_worklists()->IsEmpty());
}
// The objects reachable from the roots are marked, yet unreachable objects
// are unmarked. Mark objects reachable due to embedder heap tracing or
// harmony weak maps.
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_WEAK_CLOSURE_EPHEMERON);
ProcessEphemeronMarking();
DCHECK(local_marking_worklists()->IsEmpty());
}
// The objects reachable from the roots, weak maps, and embedder heap
// tracing are marked. Objects pointed to only by weak global handles cannot
// be immediately reclaimed. Instead, we have to mark them as pending and
// mark objects reachable from them.
//
// First we identify nonlive weak handles and mark them as pending
// destruction.
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_WEAK_CLOSURE_WEAK_HANDLES);
heap()->isolate()->global_handles()->IterateWeakRootsIdentifyFinalizers(
&IsUnmarkedHeapObject);
DrainMarkingWorklist();
}
// Process finalizers, effectively keeping them alive until the next
// garbage collection.
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_MARK_WEAK_CLOSURE_WEAK_ROOTS);
heap()->isolate()->global_handles()->IterateWeakRootsForFinalizers(
&root_visitor);
DrainMarkingWorklist();
}
// Repeat ephemeron processing from the newly marked objects.
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_MARK_WEAK_CLOSURE_HARMONY);
ProcessEphemeronMarking();
DCHECK(local_marking_worklists()->IsEmbedderEmpty());
DCHECK(local_marking_worklists()->IsEmpty());
}
{
heap()->isolate()->global_handles()->IterateWeakRootsForPhantomHandles(
&IsUnmarkedHeapObject);
}
}
if (was_marked_incrementally_) {
MarkingBarrier::DeactivateAll(heap());
}
epoch_++;
}
void MarkCompactCollector::ClearNonLiveReferences() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR);
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_STRING_TABLE);
// Prune the string table removing all strings only pointed to by the
// string table. Cannot use string_table() here because the string
// table is marked.
StringTable* string_table = isolate()->string_table();
InternalizedStringTableCleaner internalized_visitor(heap());
string_table->DropOldData();
string_table->IterateElements(&internalized_visitor);
string_table->NotifyElementsRemoved(internalized_visitor.PointersRemoved());
ExternalStringTableCleaner external_visitor(heap());
heap()->external_string_table_.IterateAll(&external_visitor);
heap()->external_string_table_.CleanUpAll();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_FLUSHABLE_BYTECODE);
ClearOldBytecodeCandidates();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_FLUSHED_JS_FUNCTIONS);
ClearFlushedJsFunctions();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_WEAK_LISTS);
// Process the weak references.
MarkCompactWeakObjectRetainer mark_compact_object_retainer(
non_atomic_marking_state());
heap()->ProcessAllWeakReferences(&mark_compact_object_retainer);
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_MAPS);
// ClearFullMapTransitions must be called before weak references are
// cleared.
ClearFullMapTransitions();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_WEAK_REFERENCES);
ClearWeakReferences();
ClearWeakCollections();
ClearJSWeakRefs();
}
MarkDependentCodeForDeoptimization();
DCHECK(weak_objects_.transition_arrays.IsEmpty());
DCHECK(weak_objects_.weak_references.IsEmpty());
DCHECK(weak_objects_.weak_objects_in_code.IsEmpty());
DCHECK(weak_objects_.js_weak_refs.IsEmpty());
DCHECK(weak_objects_.weak_cells.IsEmpty());
DCHECK(weak_objects_.bytecode_flushing_candidates.IsEmpty());
DCHECK(weak_objects_.flushed_js_functions.IsEmpty());
}
void MarkCompactCollector::MarkDependentCodeForDeoptimization() {
std::pair<HeapObject, Code> weak_object_in_code;
while (weak_objects_.weak_objects_in_code.Pop(kMainThreadTask,
&weak_object_in_code)) {
HeapObject object = weak_object_in_code.first;
Code code = weak_object_in_code.second;
if (!non_atomic_marking_state()->IsBlackOrGrey(object) &&
!code.embedded_objects_cleared()) {
if (!code.marked_for_deoptimization()) {
code.SetMarkedForDeoptimization("weak objects");
have_code_to_deoptimize_ = true;
}
code.ClearEmbeddedObjects(heap_);
DCHECK(code.embedded_objects_cleared());
}
}
}
void MarkCompactCollector::ClearPotentialSimpleMapTransition(Map dead_target) {
DCHECK(non_atomic_marking_state()->IsWhite(dead_target));
Object potential_parent = dead_target.constructor_or_backpointer();
if (potential_parent.IsMap()) {
Map parent = Map::cast(potential_parent);
DisallowHeapAllocation no_gc_obviously;
if (non_atomic_marking_state()->IsBlackOrGrey(parent) &&
TransitionsAccessor(isolate(), parent, &no_gc_obviously)
.HasSimpleTransitionTo(dead_target)) {
ClearPotentialSimpleMapTransition(parent, dead_target);
}
}
}
void MarkCompactCollector::ClearPotentialSimpleMapTransition(Map map,
Map dead_target) {
DCHECK(!map.is_prototype_map());
DCHECK(!dead_target.is_prototype_map());
DCHECK_EQ(map.raw_transitions(), HeapObjectReference::Weak(dead_target));
// Take ownership of the descriptor array.
int number_of_own_descriptors = map.NumberOfOwnDescriptors();
DescriptorArray descriptors = map.instance_descriptors(kRelaxedLoad);
if (descriptors == dead_target.instance_descriptors(kRelaxedLoad) &&
number_of_own_descriptors > 0) {
TrimDescriptorArray(map, descriptors);
DCHECK(descriptors.number_of_descriptors() == number_of_own_descriptors);
}
}
void MarkCompactCollector::FlushBytecodeFromSFI(
SharedFunctionInfo shared_info) {
DCHECK(shared_info.HasBytecodeArray());
// Retain objects required for uncompiled data.
String inferred_name = shared_info.inferred_name();
int start_position = shared_info.StartPosition();
int end_position = shared_info.EndPosition();
shared_info.DiscardCompiledMetadata(
isolate(), [](HeapObject object, ObjectSlot slot, HeapObject target) {
RecordSlot(object, slot, target);
});
// The size of the bytecode array should always be larger than an
// UncompiledData object.
STATIC_ASSERT(BytecodeArray::SizeFor(0) >=
UncompiledDataWithoutPreparseData::kSize);
// Replace bytecode array with an uncompiled data array.
HeapObject compiled_data = shared_info.GetBytecodeArray();
Address compiled_data_start = compiled_data.address();
int compiled_data_size = compiled_data.Size();
MemoryChunk* chunk = MemoryChunk::FromAddress(compiled_data_start);
// Clear any recorded slots for the compiled data as being invalid.
DCHECK_NULL(chunk->sweeping_slot_set());
RememberedSet<OLD_TO_NEW>::RemoveRange(
chunk, compiled_data_start, compiled_data_start + compiled_data_size,
SlotSet::FREE_EMPTY_BUCKETS);
RememberedSet<OLD_TO_OLD>::RemoveRange(
chunk, compiled_data_start, compiled_data_start + compiled_data_size,
SlotSet::FREE_EMPTY_BUCKETS);
// Swap the map, using set_map_after_allocation to avoid verify heap checks
// which are not necessary since we are doing this during the GC atomic pause.
compiled_data.set_map_after_allocation(
ReadOnlyRoots(heap()).uncompiled_data_without_preparse_data_map(),
SKIP_WRITE_BARRIER);
// Create a filler object for any left over space in the bytecode array.
if (!heap()->IsLargeObject(compiled_data)) {
heap()->CreateFillerObjectAt(
compiled_data.address() + UncompiledDataWithoutPreparseData::kSize,
compiled_data_size - UncompiledDataWithoutPreparseData::kSize,
ClearRecordedSlots::kNo);
}
// Initialize the uncompiled data.
UncompiledData uncompiled_data = UncompiledData::cast(compiled_data);
uncompiled_data.InitAfterBytecodeFlush(
inferred_name, start_position, end_position,
[](HeapObject object, ObjectSlot slot, HeapObject target) {
RecordSlot(object, slot, target);
});
// Mark the uncompiled data as black, and ensure all fields have already been
// marked.
DCHECK(non_atomic_marking_state()->IsBlackOrGrey(inferred_name));
non_atomic_marking_state()->WhiteToBlack(uncompiled_data);
// Use the raw function data setter to avoid validity checks, since we're
// performing the unusual task of decompiling.
shared_info.set_function_data(uncompiled_data, kReleaseStore);
DCHECK(!shared_info.is_compiled());
}
void MarkCompactCollector::ClearOldBytecodeCandidates() {
DCHECK(FLAG_flush_bytecode ||
weak_objects_.bytecode_flushing_candidates.IsEmpty());
SharedFunctionInfo flushing_candidate;
while (weak_objects_.bytecode_flushing_candidates.Pop(kMainThreadTask,
&flushing_candidate)) {
// If the BytecodeArray is dead, flush it, which will replace the field with
// an uncompiled data object.
if (!non_atomic_marking_state()->IsBlackOrGrey(
flushing_candidate.GetBytecodeArray())) {
FlushBytecodeFromSFI(flushing_candidate);
}
// Now record the slot, which has either been updated to an uncompiled data,
// or is the BytecodeArray which is still alive.
ObjectSlot slot =
flushing_candidate.RawField(SharedFunctionInfo::kFunctionDataOffset);
RecordSlot(flushing_candidate, slot, HeapObject::cast(*slot));
}
}
void MarkCompactCollector::ClearFlushedJsFunctions() {
DCHECK(FLAG_flush_bytecode || weak_objects_.flushed_js_functions.IsEmpty());
JSFunction flushed_js_function;
while (weak_objects_.flushed_js_functions.Pop(kMainThreadTask,
&flushed_js_function)) {
auto gc_notify_updated_slot = [](HeapObject object, ObjectSlot slot,
Object target) {
RecordSlot(object, slot, HeapObject::cast(target));
};
flushed_js_function.ResetIfBytecodeFlushed(gc_notify_updated_slot);
}
}
void MarkCompactCollector::ClearFullMapTransitions() {
TransitionArray array;
while (weak_objects_.transition_arrays.Pop(kMainThreadTask, &array)) {
int num_transitions = array.number_of_entries();
if (num_transitions > 0) {
Map map;
// The array might contain "undefined" elements because it's not yet
// filled. Allow it.
if (array.GetTargetIfExists(0, isolate(), &map)) {
DCHECK(!map.is_null()); // Weak pointers aren't cleared yet.
Object constructor_or_backpointer = map.constructor_or_backpointer();
if (constructor_or_backpointer.IsSmi()) {
DCHECK(isolate()->has_active_deserializer());
DCHECK_EQ(constructor_or_backpointer,
Deserializer::uninitialized_field_value());
continue;
}
Map parent = Map::cast(map.constructor_or_backpointer());
bool parent_is_alive =
non_atomic_marking_state()->IsBlackOrGrey(parent);
DescriptorArray descriptors =
parent_is_alive ? parent.instance_descriptors(kRelaxedLoad)
: DescriptorArray();
bool descriptors_owner_died =
CompactTransitionArray(parent, array, descriptors);
if (descriptors_owner_died) {
TrimDescriptorArray(parent, descriptors);
}
}
}
}
}
bool MarkCompactCollector::CompactTransitionArray(Map map,
TransitionArray transitions,
DescriptorArray descriptors) {
DCHECK(!map.is_prototype_map());
int num_transitions = transitions.number_of_entries();
bool descriptors_owner_died = false;
int transition_index = 0;
// Compact all live transitions to the left.
for (int i = 0; i < num_transitions; ++i) {
Map target = transitions.GetTarget(i);
DCHECK_EQ(target.constructor_or_backpointer(), map);
if (non_atomic_marking_state()->IsWhite(target)) {
if (!descriptors.is_null() &&
target.instance_descriptors(kRelaxedLoad) == descriptors) {
DCHECK(!target.is_prototype_map());
descriptors_owner_died = true;
}
} else {
if (i != transition_index) {
Name key = transitions.GetKey(i);
transitions.SetKey(transition_index, key);
HeapObjectSlot key_slot = transitions.GetKeySlot(transition_index);
RecordSlot(transitions, key_slot, key);
MaybeObject raw_target = transitions.GetRawTarget(i);
transitions.SetRawTarget(transition_index, raw_target);
HeapObjectSlot target_slot =
transitions.GetTargetSlot(transition_index);
RecordSlot(transitions, target_slot, raw_target->GetHeapObject());
}
transition_index++;
}
}
// If there are no transitions to be cleared, return.
if (transition_index == num_transitions) {
DCHECK(!descriptors_owner_died);
return false;
}
// Note that we never eliminate a transition array, though we might right-trim
// such that number_of_transitions() == 0. If this assumption changes,
// TransitionArray::Insert() will need to deal with the case that a transition
// array disappeared during GC.
int trim = transitions.Capacity() - transition_index;
if (trim > 0) {
heap_->RightTrimWeakFixedArray(transitions,
trim * TransitionArray::kEntrySize);
transitions.SetNumberOfTransitions(transition_index);
}
return descriptors_owner_died;
}
void MarkCompactCollector::RightTrimDescriptorArray(DescriptorArray array,
int descriptors_to_trim) {
int old_nof_all_descriptors = array.number_of_all_descriptors();
int new_nof_all_descriptors = old_nof_all_descriptors - descriptors_to_trim;
DCHECK_LT(0, descriptors_to_trim);
DCHECK_LE(0, new_nof_all_descriptors);
Address start = array.GetDescriptorSlot(new_nof_all_descriptors).address();
Address end = array.GetDescriptorSlot(old_nof_all_descriptors).address();
MemoryChunk* chunk = MemoryChunk::FromHeapObject(array);
DCHECK_NULL(chunk->sweeping_slot_set());
RememberedSet<OLD_TO_NEW>::RemoveRange(chunk, start, end,
SlotSet::FREE_EMPTY_BUCKETS);
RememberedSet<OLD_TO_OLD>::RemoveRange(chunk, start, end,
SlotSet::FREE_EMPTY_BUCKETS);
heap()->CreateFillerObjectAt(start, static_cast<int>(end - start),
ClearRecordedSlots::kNo);
array.set_number_of_all_descriptors(new_nof_all_descriptors);
}
void MarkCompactCollector::TrimDescriptorArray(Map map,
DescriptorArray descriptors) {
int number_of_own_descriptors = map.NumberOfOwnDescriptors();
if (number_of_own_descriptors == 0) {
DCHECK(descriptors == ReadOnlyRoots(heap_).empty_descriptor_array());
return;
}
// TODO(ulan): Trim only if slack is greater than some percentage threshold.
int to_trim =
descriptors.number_of_all_descriptors() - number_of_own_descriptors;
if (to_trim > 0) {
descriptors.set_number_of_descriptors(number_of_own_descriptors);
RightTrimDescriptorArray(descriptors, to_trim);
TrimEnumCache(map, descriptors);
descriptors.Sort();
if (FLAG_unbox_double_fields) {
LayoutDescriptor layout_descriptor = map.layout_descriptor(kAcquireLoad);
layout_descriptor = layout_descriptor.Trim(heap_, map, descriptors,
number_of_own_descriptors);
SLOW_DCHECK(layout_descriptor.IsConsistentWithMap(map, true));
}
}
DCHECK(descriptors.number_of_descriptors() == number_of_own_descriptors);
map.set_owns_descriptors(true);
}
void MarkCompactCollector::TrimEnumCache(Map map, DescriptorArray descriptors) {
int live_enum = map.EnumLength();
if (live_enum == kInvalidEnumCacheSentinel) {
live_enum = map.NumberOfEnumerableProperties();
}
if (live_enum == 0) return descriptors.ClearEnumCache();
EnumCache enum_cache = descriptors.enum_cache();
FixedArray keys = enum_cache.keys();
int to_trim = keys.length() - live_enum;
if (to_trim <= 0) return;
heap_->RightTrimFixedArray(keys, to_trim);
FixedArray indices = enum_cache.indices();
to_trim = indices.length() - live_enum;
if (to_trim <= 0) return;
heap_->RightTrimFixedArray(indices, to_trim);
}
void MarkCompactCollector::ClearWeakCollections() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_WEAK_COLLECTIONS);
EphemeronHashTable table;
while (weak_objects_.ephemeron_hash_tables.Pop(kMainThreadTask, &table)) {
for (InternalIndex i : table.IterateEntries()) {
HeapObject key = HeapObject::cast(table.KeyAt(i));
#ifdef VERIFY_HEAP
if (FLAG_verify_heap) {
Object value = table.ValueAt(i);
if (value.IsHeapObject()) {
CHECK_IMPLIES(non_atomic_marking_state()->IsBlackOrGrey(key),
non_atomic_marking_state()->IsBlackOrGrey(
HeapObject::cast(value)));
}
}
#endif
if (!non_atomic_marking_state()->IsBlackOrGrey(key)) {
table.RemoveEntry(i);
}
}
}
for (auto it = heap_->ephemeron_remembered_set_.begin();
it != heap_->ephemeron_remembered_set_.end();) {
if (!non_atomic_marking_state()->IsBlackOrGrey(it->first)) {
it = heap_->ephemeron_remembered_set_.erase(it);
} else {
++it;
}
}
}
void MarkCompactCollector::ClearWeakReferences() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_CLEAR_WEAK_REFERENCES);
std::pair<HeapObject, HeapObjectSlot> slot;
HeapObjectReference cleared_weak_ref =
HeapObjectReference::ClearedValue(isolate());
while (weak_objects_.weak_references.Pop(kMainThreadTask, &slot)) {
HeapObject value;
// The slot could have been overwritten, so we have to treat it
// as MaybeObjectSlot.
MaybeObjectSlot location(slot.second);
if ((*location)->GetHeapObjectIfWeak(&value)) {
DCHECK(!value.IsCell());
if (non_atomic_marking_state()->IsBlackOrGrey(value)) {
// The value of the weak reference is alive.
RecordSlot(slot.first, HeapObjectSlot(location), value);
} else {
if (value.IsMap()) {
// The map is non-live.
ClearPotentialSimpleMapTransition(Map::cast(value));
}
location.store(cleared_weak_ref);
}
}
}
}
void MarkCompactCollector::ClearJSWeakRefs() {
if (!FLAG_harmony_weak_refs) {
return;
}
JSWeakRef weak_ref;
while (weak_objects_.js_weak_refs.Pop(kMainThreadTask, &weak_ref)) {
HeapObject target = HeapObject::cast(weak_ref.target());
if (!non_atomic_marking_state()->IsBlackOrGrey(target)) {
weak_ref.set_target(ReadOnlyRoots(isolate()).undefined_value());
} else {
// The value of the JSWeakRef is alive.
ObjectSlot slot = weak_ref.RawField(JSWeakRef::kTargetOffset);
RecordSlot(weak_ref, slot, target);
}
}
WeakCell weak_cell;
while (weak_objects_.weak_cells.Pop(kMainThreadTask, &weak_cell)) {
auto gc_notify_updated_slot = [](HeapObject object, ObjectSlot slot,
Object target) {
if (target.IsHeapObject()) {
RecordSlot(object, slot, HeapObject::cast(target));
}
};
HeapObject target = HeapObject::cast(weak_cell.target());
if (!non_atomic_marking_state()->IsBlackOrGrey(target)) {
DCHECK(!target.IsUndefined());
// The value of the WeakCell is dead.
JSFinalizationRegistry finalization_registry =
JSFinalizationRegistry::cast(weak_cell.finalization_registry());
if (!finalization_registry.scheduled_for_cleanup()) {
heap()->EnqueueDirtyJSFinalizationRegistry(finalization_registry,
gc_notify_updated_slot);
}
// We're modifying the pointers in WeakCell and JSFinalizationRegistry
// during GC; thus we need to record the slots it writes. The normal write
// barrier is not enough, since it's disabled before GC.
weak_cell.Nullify(isolate(), gc_notify_updated_slot);
DCHECK(finalization_registry.NeedsCleanup());
DCHECK(finalization_registry.scheduled_for_cleanup());
} else {
// The value of the WeakCell is alive.
ObjectSlot slot = weak_cell.RawField(WeakCell::kTargetOffset);
RecordSlot(weak_cell, slot, HeapObject::cast(*slot));
}
HeapObject unregister_token =
HeapObject::cast(weak_cell.unregister_token());
if (!non_atomic_marking_state()->IsBlackOrGrey(unregister_token)) {
// The unregister token is dead. Remove any corresponding entries in the
// key map. Multiple WeakCell with the same token will have all their
// unregister_token field set to undefined when processing the first
// WeakCell. Like above, we're modifying pointers during GC, so record the
// slots.
HeapObject undefined = ReadOnlyRoots(isolate()).undefined_value();
JSFinalizationRegistry finalization_registry =
JSFinalizationRegistry::cast(weak_cell.finalization_registry());
finalization_registry.RemoveUnregisterToken(
JSReceiver::cast(unregister_token), isolate(),
[undefined](WeakCell matched_cell) {
matched_cell.set_unregister_token(undefined);
},
gc_notify_updated_slot);
// The following is necessary because in the case that weak_cell has
// already been popped and removed from the FinalizationRegistry, the call
// to JSFinalizationRegistry::RemoveUnregisterToken above will not find
// weak_cell itself to clear its unregister token.
weak_cell.set_unregister_token(undefined);
} else {
// The unregister_token is alive.
ObjectSlot slot = weak_cell.RawField(WeakCell::kUnregisterTokenOffset);
RecordSlot(weak_cell, slot, HeapObject::cast(*slot));
}
}
heap()->PostFinalizationRegistryCleanupTaskIfNeeded();
}
void MarkCompactCollector::AbortWeakObjects() {
weak_objects_.transition_arrays.Clear();
weak_objects_.ephemeron_hash_tables.Clear();
weak_objects_.current_ephemerons.Clear();
weak_objects_.next_ephemerons.Clear();
weak_objects_.discovered_ephemerons.Clear();
weak_objects_.weak_references.Clear();
weak_objects_.weak_objects_in_code.Clear();
weak_objects_.js_weak_refs.Clear();
weak_objects_.weak_cells.Clear();
weak_objects_.bytecode_flushing_candidates.Clear();
weak_objects_.flushed_js_functions.Clear();
}
bool MarkCompactCollector::IsOnEvacuationCandidate(MaybeObject obj) {
return Page::FromAddress(obj.ptr())->IsEvacuationCandidate();
}
MarkCompactCollector::RecordRelocSlotInfo
MarkCompactCollector::PrepareRecordRelocSlot(Code host, RelocInfo* rinfo,
HeapObject target) {
RecordRelocSlotInfo result;
result.should_record = false;
Page* target_page = Page::FromHeapObject(target);
Page* source_page = Page::FromHeapObject(host);
if (target_page->IsEvacuationCandidate() &&
(rinfo->host().is_null() ||
!source_page->ShouldSkipEvacuationSlotRecording())) {
RelocInfo::Mode rmode = rinfo->rmode();
Address addr = rinfo->pc();
SlotType slot_type = SlotTypeForRelocInfoMode(rmode);
if (rinfo->IsInConstantPool()) {
addr = rinfo->constant_pool_entry_address();
if (RelocInfo::IsCodeTargetMode(rmode)) {
slot_type = CODE_ENTRY_SLOT;
} else if (RelocInfo::IsCompressedEmbeddedObject(rmode)) {
slot_type = COMPRESSED_OBJECT_SLOT;
} else {
DCHECK(RelocInfo::IsFullEmbeddedObject(rmode));
slot_type = FULL_OBJECT_SLOT;
}
}
uintptr_t offset = addr - source_page->address();
DCHECK_LT(offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset));
result.should_record = true;
result.memory_chunk = source_page;
result.slot_type = slot_type;
result.offset = static_cast<uint32_t>(offset);
}
return result;
}
void MarkCompactCollector::RecordRelocSlot(Code host, RelocInfo* rinfo,
HeapObject target) {
RecordRelocSlotInfo info = PrepareRecordRelocSlot(host, rinfo, target);
if (info.should_record) {
RememberedSet<OLD_TO_OLD>::InsertTyped(info.memory_chunk, info.slot_type,
info.offset);
}
}
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(HeapObject heap_object);
template <>
Object MakeSlotValue<ObjectSlot, HeapObjectReferenceType::STRONG>(
HeapObject heap_object) {
return heap_object;
}
template <>
MaybeObject MakeSlotValue<MaybeObjectSlot, HeapObjectReferenceType::STRONG>(
HeapObject heap_object) {
return HeapObjectReference::Strong(heap_object);
}
template <>
MaybeObject MakeSlotValue<MaybeObjectSlot, HeapObjectReferenceType::WEAK>(
HeapObject heap_object) {
return HeapObjectReference::Weak(heap_object);
}
template <>
Object MakeSlotValue<OffHeapObjectSlot, HeapObjectReferenceType::STRONG>(
HeapObject heap_object) {
return heap_object;
}
#ifdef V8_COMPRESS_POINTERS
template <>
Object MakeSlotValue<FullObjectSlot, HeapObjectReferenceType::STRONG>(
HeapObject heap_object) {
return heap_object;
}
template <>
MaybeObject MakeSlotValue<FullMaybeObjectSlot, HeapObjectReferenceType::STRONG>(
HeapObject heap_object) {
return HeapObjectReference::Strong(heap_object);
}
// The following specialization
// MakeSlotValue<FullMaybeObjectSlot, HeapObjectReferenceType::WEAK>()
// is not used.
#endif
template <AccessMode access_mode, HeapObjectReferenceType reference_type,
typename TSlot>
static inline SlotCallbackResult UpdateSlot(TSlot slot,
typename TSlot::TObject old,
HeapObject heap_obj) {
static_assert(std::is_same<TSlot, FullObjectSlot>::value ||
std::is_same<TSlot, ObjectSlot>::value ||
std::is_same<TSlot, FullMaybeObjectSlot>::value ||
std::is_same<TSlot, MaybeObjectSlot>::value ||
std::is_same<TSlot, OffHeapObjectSlot>::value,
"Only [Full|OffHeap]ObjectSlot and [Full]MaybeObjectSlot are "
"expected here");
MapWord map_word = heap_obj.map_word();
if (map_word.IsForwardingAddress()) {
DCHECK_IMPLIES(!Heap::InFromPage(heap_obj),
MarkCompactCollector::IsOnEvacuationCandidate(heap_obj) ||
Page::FromHeapObject(heap_obj)->IsFlagSet(
Page::COMPACTION_WAS_ABORTED));
typename TSlot::TObject target =
MakeSlotValue<TSlot, reference_type>(map_word.ToForwardingAddress());
if (access_mode == AccessMode::NON_ATOMIC) {
slot.store(target);
} else {
slot.Release_CompareAndSwap(old, target);
}
DCHECK(!Heap::InFromPage(target));
DCHECK(!MarkCompactCollector::IsOnEvacuationCandidate(target));
} else {
DCHECK(heap_obj.map().IsMap());
}
// OLD_TO_OLD slots are always removed after updating.
return REMOVE_SLOT;
}
template <AccessMode access_mode, typename TSlot>
static inline SlotCallbackResult UpdateSlot(IsolateRoot isolate, TSlot slot) {
typename TSlot::TObject obj = slot.Relaxed_Load(isolate);
HeapObject heap_obj;
if (TSlot::kCanBeWeak && obj->GetHeapObjectIfWeak(&heap_obj)) {
UpdateSlot<access_mode, HeapObjectReferenceType::WEAK>(slot, obj, heap_obj);
} else if (obj->GetHeapObjectIfStrong(&heap_obj)) {
return UpdateSlot<access_mode, HeapObjectReferenceType::STRONG>(slot, obj,
heap_obj);
}
return REMOVE_SLOT;
}
template <AccessMode access_mode, typename TSlot>
static inline SlotCallbackResult UpdateStrongSlot(IsolateRoot isolate,
TSlot slot) {
typename TSlot::TObject obj = slot.Relaxed_Load(isolate);
DCHECK(!HAS_WEAK_HEAP_OBJECT_TAG(obj.ptr()));
HeapObject heap_obj;
if (obj.GetHeapObject(&heap_obj)) {
return UpdateSlot<access_mode, HeapObjectReferenceType::STRONG>(slot, obj,
heap_obj);
}
return REMOVE_SLOT;
}
} // namespace
// Visitor for updating root pointers and to-space pointers.
// It does not expect to encounter pointers to dead objects.
class PointersUpdatingVisitor : public ObjectVisitor, public RootVisitor {
public:
explicit PointersUpdatingVisitor(IsolateRoot isolate) : isolate_(isolate) {}
void VisitPointer(HeapObject host, ObjectSlot p) override {
UpdateStrongSlotInternal(isolate_, p);
}
void VisitPointer(HeapObject host, MaybeObjectSlot p) override {
UpdateSlotInternal(isolate_, p);
}
void VisitPointers(HeapObject host, ObjectSlot start,
ObjectSlot end) override {
for (ObjectSlot p = start; p < end; ++p) {
UpdateStrongSlotInternal(isolate_, p);
}
}
void VisitPointers(HeapObject host, MaybeObjectSlot start,
MaybeObjectSlot end) final {
for (MaybeObjectSlot p = start; p < end; ++p) {
UpdateSlotInternal(isolate_, p);
}
}
void VisitRootPointer(Root root, const char* description,
FullObjectSlot p) override {
UpdateRootSlotInternal(isolate_, p);
}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) override {
for (FullObjectSlot p = start; p < end; ++p) {
UpdateRootSlotInternal(isolate_, p);
}
}
void VisitRootPointers(Root root, const char* description,
OffHeapObjectSlot start,
OffHeapObjectSlot end) override {
for (OffHeapObjectSlot p = start; p < end; ++p) {
UpdateRootSlotInternal(isolate_, p);
}
}
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
// This visitor nevers visits code objects.
UNREACHABLE();
}
void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
// This visitor nevers visits code objects.
UNREACHABLE();
}
private:
static inline SlotCallbackResult UpdateRootSlotInternal(IsolateRoot isolate,
FullObjectSlot slot) {
return UpdateStrongSlot<AccessMode::NON_ATOMIC>(isolate, slot);
}
static inline SlotCallbackResult UpdateRootSlotInternal(
IsolateRoot isolate, OffHeapObjectSlot slot) {
return UpdateStrongSlot<AccessMode::NON_ATOMIC>(isolate, slot);
}
static inline SlotCallbackResult UpdateStrongMaybeObjectSlotInternal(
IsolateRoot isolate, MaybeObjectSlot slot) {
return UpdateStrongSlot<AccessMode::NON_ATOMIC>(isolate, slot);
}
static inline SlotCallbackResult UpdateStrongSlotInternal(IsolateRoot isolate,
ObjectSlot slot) {
return UpdateStrongSlot<AccessMode::NON_ATOMIC>(isolate, slot);
}
static inline SlotCallbackResult UpdateSlotInternal(IsolateRoot isolate,
MaybeObjectSlot slot) {
return UpdateSlot<AccessMode::NON_ATOMIC>(isolate, slot);
}
IsolateRoot isolate_;
};
static String UpdateReferenceInExternalStringTableEntry(Heap* heap,
FullObjectSlot p) {
MapWord map_word = HeapObject::cast(*p).map_word();
if (map_word.IsForwardingAddress()) {
String new_string = String::cast(map_word.ToForwardingAddress());
if (new_string.IsExternalString()) {
MemoryChunk::MoveExternalBackingStoreBytes(
ExternalBackingStoreType::kExternalString,
Page::FromAddress((*p).ptr()), Page::FromHeapObject(new_string),
ExternalString::cast(new_string).ExternalPayloadSize());
}
return new_string;
}
return String::cast(*p);
}
void MarkCompactCollector::EvacuatePrologue() {
// New space.
NewSpace* new_space = heap()->new_space();
// Append the list of new space pages to be processed.
for (Page* p :
PageRange(new_space->first_allocatable_address(), new_space->top())) {
new_space_evacuation_pages_.push_back(p);
}
new_space->Flip();
new_space->ResetLinearAllocationArea();
DCHECK_EQ(new_space->Size(), 0);
heap()->new_lo_space()->Flip();
heap()->new_lo_space()->ResetPendingObject();
// Old space.
DCHECK(old_space_evacuation_pages_.empty());
old_space_evacuation_pages_ = std::move(evacuation_candidates_);
evacuation_candidates_.clear();
DCHECK(evacuation_candidates_.empty());
}
void MarkCompactCollector::EvacuateEpilogue() {
aborted_evacuation_candidates_.clear();
// New space.
heap()->new_space()->set_age_mark(heap()->new_space()->top());
DCHECK_IMPLIES(FLAG_always_promote_young_mc,
heap()->new_space()->Size() == 0);
// Deallocate unmarked large objects.
heap()->lo_space()->FreeUnmarkedObjects();
heap()->code_lo_space()->FreeUnmarkedObjects();
heap()->new_lo_space()->FreeUnmarkedObjects();
// Old space. Deallocate evacuated candidate pages.
ReleaseEvacuationCandidates();
// Give pages that are queued to be freed back to the OS.
heap()->memory_allocator()->unmapper()->FreeQueuedChunks();
#ifdef DEBUG
// Old-to-old slot sets must be empty after evacuation.
for (Page* p : *heap()->old_space()) {
DCHECK_NULL((p->slot_set<OLD_TO_OLD, AccessMode::ATOMIC>()));
DCHECK_NULL((p->typed_slot_set<OLD_TO_OLD, AccessMode::ATOMIC>()));
DCHECK_NULL(p->invalidated_slots<OLD_TO_OLD>());
DCHECK_NULL(p->invalidated_slots<OLD_TO_NEW>());
}
#endif
}
class Evacuator : public Malloced {
public:
enum EvacuationMode {
kObjectsNewToOld,
kPageNewToOld,
kObjectsOldToOld,
kPageNewToNew,
};
static const char* EvacuationModeName(EvacuationMode mode) {
switch (mode) {
case kObjectsNewToOld:
return "objects-new-to-old";
case kPageNewToOld:
return "page-new-to-old";
case kObjectsOldToOld:
return "objects-old-to-old";
case kPageNewToNew:
return "page-new-to-new";
}
}
static inline EvacuationMode ComputeEvacuationMode(MemoryChunk* chunk) {
// Note: The order of checks is important in this function.
if (chunk->IsFlagSet(MemoryChunk::PAGE_NEW_OLD_PROMOTION))
return kPageNewToOld;
if (chunk->IsFlagSet(MemoryChunk::PAGE_NEW_NEW_PROMOTION))
return kPageNewToNew;
if (chunk->InYoungGeneration()) return kObjectsNewToOld;
return kObjectsOldToOld;
}
// NewSpacePages with more live bytes than this threshold qualify for fast
// evacuation.
static intptr_t NewSpacePageEvacuationThreshold() {
if (FLAG_page_promotion)
return FLAG_page_promotion_threshold *
MemoryChunkLayout::AllocatableMemoryInDataPage() / 100;
return MemoryChunkLayout::AllocatableMemoryInDataPage() + kTaggedSize;
}
Evacuator(Heap* heap, RecordMigratedSlotVisitor* record_visitor,
EvacuationAllocator* local_allocator, bool always_promote_young)
: heap_(heap),
local_pretenuring_feedback_(kInitialLocalPretenuringFeedbackCapacity),
new_space_visitor_(heap_, local_allocator, record_visitor,
&local_pretenuring_feedback_, always_promote_young),
new_to_new_page_visitor_(heap_, record_visitor,
&local_pretenuring_feedback_),
new_to_old_page_visitor_(heap_, record_visitor,
&local_pretenuring_feedback_),
old_space_visitor_(heap_, local_allocator, record_visitor),
local_allocator_(local_allocator),
duration_(0.0),
bytes_compacted_(0) {}
virtual ~Evacuator() = default;
void EvacuatePage(MemoryChunk* chunk);
void AddObserver(MigrationObserver* observer) {
new_space_visitor_.AddObserver(observer);
old_space_visitor_.AddObserver(observer);
}
// Merge back locally cached info sequentially. Note that this method needs
// to be called from the main thread.
virtual void Finalize();
virtual GCTracer::BackgroundScope::ScopeId GetBackgroundTracingScope() = 0;
virtual GCTracer::Scope::ScopeId GetTracingScope() = 0;
protected:
static const int kInitialLocalPretenuringFeedbackCapacity = 256;
// |saved_live_bytes| returns the live bytes of the page that was processed.
virtual void RawEvacuatePage(MemoryChunk* chunk,
intptr_t* saved_live_bytes) = 0;
inline Heap* heap() { return heap_; }
void ReportCompactionProgress(double duration, intptr_t bytes_compacted) {
duration_ += duration;
bytes_compacted_ += bytes_compacted;
}
Heap* heap_;
Heap::PretenuringFeedbackMap local_pretenuring_feedback_;
// Visitors for the corresponding spaces.
EvacuateNewSpaceVisitor new_space_visitor_;
EvacuateNewSpacePageVisitor<PageEvacuationMode::NEW_TO_NEW>
new_to_new_page_visitor_;
EvacuateNewSpacePageVisitor<PageEvacuationMode::NEW_TO_OLD>
new_to_old_page_visitor_;
EvacuateOldSpaceVisitor old_space_visitor_;
// Locally cached collector data.
EvacuationAllocator* local_allocator_;
// Book keeping info.
double duration_;
intptr_t bytes_compacted_;
};
void Evacuator::EvacuatePage(MemoryChunk* chunk) {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"), "Evacuator::EvacuatePage");
DCHECK(chunk->SweepingDone());
intptr_t saved_live_bytes = 0;
double evacuation_time = 0.0;
{
AlwaysAllocateScope always_allocate(heap());
TimedScope timed_scope(&evacuation_time);
RawEvacuatePage(chunk, &saved_live_bytes);
}
ReportCompactionProgress(evacuation_time, saved_live_bytes);
if (FLAG_trace_evacuation) {
PrintIsolate(heap()->isolate(),
"evacuation[%p]: page=%p new_space=%d "
"page_evacuation=%d executable=%d contains_age_mark=%d "
"live_bytes=%" V8PRIdPTR " time=%f success=%d\n",
static_cast<void*>(this), static_cast<void*>(chunk),
chunk->InNewSpace(),
chunk->IsFlagSet(Page::PAGE_NEW_OLD_PROMOTION) ||
chunk->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION),
chunk->IsFlagSet(MemoryChunk::IS_EXECUTABLE),
chunk->Contains(heap()->new_space()->age_mark()),
saved_live_bytes, evacuation_time,
chunk->IsFlagSet(Page::COMPACTION_WAS_ABORTED));
}
}
void Evacuator::Finalize() {
local_allocator_->Finalize();
heap()->tracer()->AddCompactionEvent(duration_, bytes_compacted_);
heap()->IncrementPromotedObjectsSize(new_space_visitor_.promoted_size() +
new_to_old_page_visitor_.moved_bytes());
heap()->IncrementSemiSpaceCopiedObjectSize(
new_space_visitor_.semispace_copied_size() +
new_to_new_page_visitor_.moved_bytes());
heap()->IncrementYoungSurvivorsCounter(
new_space_visitor_.promoted_size() +
new_space_visitor_.semispace_copied_size() +
new_to_old_page_visitor_.moved_bytes() +
new_to_new_page_visitor_.moved_bytes());
heap()->MergeAllocationSitePretenuringFeedback(local_pretenuring_feedback_);
}
class FullEvacuator : public Evacuator {
public:
explicit FullEvacuator(MarkCompactCollector* collector)
: Evacuator(collector->heap(), &record_visitor_, &local_allocator_,
FLAG_always_promote_young_mc),
record_visitor_(collector, &ephemeron_remembered_set_),
local_allocator_(heap_, LocalSpaceKind::kCompactionSpaceForMarkCompact),
collector_(collector) {}
GCTracer::BackgroundScope::ScopeId GetBackgroundTracingScope() override {
return GCTracer::BackgroundScope::MC_BACKGROUND_EVACUATE_COPY;
}
GCTracer::Scope::ScopeId GetTracingScope() override {
return GCTracer::Scope::MC_EVACUATE_COPY_PARALLEL;
}
void Finalize() override {
Evacuator::Finalize();
for (auto it = ephemeron_remembered_set_.begin();
it != ephemeron_remembered_set_.end(); ++it) {
auto insert_result =
heap()->ephemeron_remembered_set_.insert({it->first, it->second});
if (!insert_result.second) {
// Insertion didn't happen, there was already an item.
auto set = insert_result.first->second;
for (int entry : it->second) {
set.insert(entry);
}
}
}
}
protected:
void RawEvacuatePage(MemoryChunk* chunk, intptr_t* live_bytes) override;
EphemeronRememberedSet ephemeron_remembered_set_;
RecordMigratedSlotVisitor record_visitor_;
EvacuationAllocator local_allocator_;
MarkCompactCollector* collector_;
};
void FullEvacuator::RawEvacuatePage(MemoryChunk* chunk, intptr_t* live_bytes) {
const EvacuationMode evacuation_mode = ComputeEvacuationMode(chunk);
MarkCompactCollector::NonAtomicMarkingState* marking_state =
collector_->non_atomic_marking_state();
*live_bytes = marking_state->live_bytes(chunk);
TRACE_EVENT2(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"FullEvacuator::RawEvacuatePage", "evacuation_mode",
EvacuationModeName(evacuation_mode), "live_bytes", *live_bytes);
HeapObject failed_object;
switch (evacuation_mode) {
case kObjectsNewToOld:
LiveObjectVisitor::VisitBlackObjectsNoFail(
chunk, marking_state, &new_space_visitor_,
LiveObjectVisitor::kClearMarkbits);
break;
case kPageNewToOld:
LiveObjectVisitor::VisitBlackObjectsNoFail(
chunk, marking_state, &new_to_old_page_visitor_,
LiveObjectVisitor::kKeepMarking);
new_to_old_page_visitor_.account_moved_bytes(
marking_state->live_bytes(chunk));
break;
case kPageNewToNew:
LiveObjectVisitor::VisitBlackObjectsNoFail(
chunk, marking_state, &new_to_new_page_visitor_,
LiveObjectVisitor::kKeepMarking);
new_to_new_page_visitor_.account_moved_bytes(
marking_state->live_bytes(chunk));
break;
case kObjectsOldToOld: {
const bool success = LiveObjectVisitor::VisitBlackObjects(
chunk, marking_state, &old_space_visitor_,
LiveObjectVisitor::kClearMarkbits, &failed_object);
if (!success) {
// Aborted compaction page. Actual processing happens on the main
// thread for simplicity reasons.
collector_->ReportAbortedEvacuationCandidate(failed_object, chunk);
}
break;
}
}
}
class PageEvacuationJob : public v8::JobTask {
public:
PageEvacuationJob(
Isolate* isolate, std::vector<std::unique_ptr<Evacuator>>* evacuators,
std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> evacuation_items)
: evacuators_(evacuators),
evacuation_items_(std::move(evacuation_items)),
remaining_evacuation_items_(evacuation_items_.size()),
generator_(evacuation_items_.size()),
tracer_(isolate->heap()->tracer()) {}
void Run(JobDelegate* delegate) override {
Evacuator* evacuator = (*evacuators_)[delegate->GetTaskId()].get();
if (delegate->IsJoiningThread()) {
TRACE_GC(tracer_, evacuator->GetTracingScope());
ProcessItems(delegate, evacuator);
} else {
TRACE_BACKGROUND_GC(tracer_, evacuator->GetBackgroundTracingScope());
ProcessItems(delegate, evacuator);
}
}
void ProcessItems(JobDelegate* delegate, Evacuator* evacuator) {
while (remaining_evacuation_items_.load(std::memory_order_relaxed) > 0) {
base::Optional<size_t> index = generator_.GetNext();
if (!index) return;
for (size_t i = *index; i < evacuation_items_.size(); ++i) {
auto& work_item = evacuation_items_[i];
if (!work_item.first.TryAcquire()) break;
evacuator->EvacuatePage(work_item.second);
if (remaining_evacuation_items_.fetch_sub(
1, std::memory_order_relaxed) <= 1) {
return;
}
}
}
}
size_t GetMaxConcurrency(size_t worker_count) const override {
const size_t kItemsPerWorker = MB / Page::kPageSize;
// Ceiling division to ensure enough workers for all
// |remaining_evacuation_items_|
const size_t wanted_num_workers =
(remaining_evacuation_items_.load(std::memory_order_relaxed) +
kItemsPerWorker - 1) /
kItemsPerWorker;
return std::min<size_t>(wanted_num_workers, evacuators_->size());
}
private:
std::vector<std::unique_ptr<Evacuator>>* evacuators_;
std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> evacuation_items_;
std::atomic<size_t> remaining_evacuation_items_{0};
IndexGenerator generator_;
GCTracer* tracer_;
};
template <class Evacuator, class Collector>
void MarkCompactCollectorBase::CreateAndExecuteEvacuationTasks(
Collector* collector,
std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> evacuation_items,
MigrationObserver* migration_observer, const intptr_t live_bytes) {
// Used for trace summary.
double compaction_speed = 0;
if (FLAG_trace_evacuation) {
compaction_speed = heap()->tracer()->CompactionSpeedInBytesPerMillisecond();
}
const bool profiling = isolate()->LogObjectRelocation();
ProfilingMigrationObserver profiling_observer(heap());
const size_t pages_count = evacuation_items.size();
std::vector<std::unique_ptr<v8::internal::Evacuator>> evacuators;
const int wanted_num_tasks = NumberOfParallelCompactionTasks();
for (int i = 0; i < wanted_num_tasks; i++) {
auto evacuator = std::make_unique<Evacuator>(collector);
if (profiling) evacuator->AddObserver(&profiling_observer);
if (migration_observer != nullptr)
evacuator->AddObserver(migration_observer);
evacuators.push_back(std::move(evacuator));
}
V8::GetCurrentPlatform()
->PostJob(v8::TaskPriority::kUserBlocking,
std::make_unique<PageEvacuationJob>(
isolate(), &evacuators, std::move(evacuation_items)))
->Join();
for (auto& evacuator : evacuators) evacuator->Finalize();
evacuators.clear();
if (FLAG_trace_evacuation) {
PrintIsolate(isolate(),
"%8.0f ms: evacuation-summary: parallel=%s pages=%zu "
"wanted_tasks=%d cores=%d live_bytes=%" V8PRIdPTR
" compaction_speed=%.f\n",
isolate()->time_millis_since_init(),
FLAG_parallel_compaction ? "yes" : "no", pages_count,
wanted_num_tasks,
V8::GetCurrentPlatform()->NumberOfWorkerThreads() + 1,
live_bytes, compaction_speed);
}
}
bool MarkCompactCollectorBase::ShouldMovePage(Page* p, intptr_t live_bytes,
bool always_promote_young) {
const bool reduce_memory = heap()->ShouldReduceMemory();
const Address age_mark = heap()->new_space()->age_mark();
return !reduce_memory && !p->NeverEvacuate() &&
(live_bytes > Evacuator::NewSpacePageEvacuationThreshold()) &&
(always_promote_young || !p->Contains(age_mark)) &&
heap()->CanExpandOldGeneration(live_bytes);
}
void MarkCompactCollector::EvacuatePagesInParallel() {
std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> evacuation_items;
intptr_t live_bytes = 0;
// Evacuation of new space pages cannot be aborted, so it needs to run
// before old space evacuation.
for (Page* page : new_space_evacuation_pages_) {
intptr_t live_bytes_on_page = non_atomic_marking_state()->live_bytes(page);
if (live_bytes_on_page == 0) continue;
live_bytes += live_bytes_on_page;
if (ShouldMovePage(page, live_bytes_on_page,
FLAG_always_promote_young_mc)) {
if (page->IsFlagSet(MemoryChunk::NEW_SPACE_BELOW_AGE_MARK) ||
FLAG_always_promote_young_mc) {
EvacuateNewSpacePageVisitor<NEW_TO_OLD>::Move(page);
DCHECK_EQ(heap()->old_space(), page->owner());
// The move added page->allocated_bytes to the old space, but we are
// going to sweep the page and add page->live_byte_count.
heap()->old_space()->DecreaseAllocatedBytes(page->allocated_bytes(),
page);
} else {
EvacuateNewSpacePageVisitor<NEW_TO_NEW>::Move(page);
}
}
evacuation_items.emplace_back(ParallelWorkItem{}, page);
}
for (Page* page : old_space_evacuation_pages_) {
live_bytes += non_atomic_marking_state()->live_bytes(page);
evacuation_items.emplace_back(ParallelWorkItem{}, page);
}
// Promote young generation large objects.
IncrementalMarking::NonAtomicMarkingState* marking_state =
heap()->incremental_marking()->non_atomic_marking_state();
for (auto it = heap()->new_lo_space()->begin();
it != heap()->new_lo_space()->end();) {
LargePage* current = *it;
it++;
HeapObject object = current->GetObject();
DCHECK(!marking_state->IsGrey(object));
if (marking_state->IsBlack(object)) {
heap_->lo_space()->PromoteNewLargeObject(current);
current->SetFlag(Page::PAGE_NEW_OLD_PROMOTION);
evacuation_items.emplace_back(ParallelWorkItem{}, current);
}
}
if (evacuation_items.empty()) return;
TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"MarkCompactCollector::EvacuatePagesInParallel", "pages",
evacuation_items.size());
CreateAndExecuteEvacuationTasks<FullEvacuator>(
this, std::move(evacuation_items), nullptr, live_bytes);
// After evacuation there might still be swept pages that weren't
// added to one of the compaction space but still reside in the
// sweeper's swept_list_. Merge remembered sets for those pages as
// well such that after mark-compact all pages either store slots
// in the sweeping or old-to-new remembered set.
sweeper()->MergeOldToNewRememberedSetsForSweptPages();
PostProcessEvacuationCandidates();
}
class EvacuationWeakObjectRetainer : public WeakObjectRetainer {
public:
Object RetainAs(Object object) override {
if (object.IsHeapObject()) {
HeapObject heap_object = HeapObject::cast(object);
MapWord map_word = heap_object.map_word();
if (map_word.IsForwardingAddress()) {
return map_word.ToForwardingAddress();
}
}
return object;
}
};
void MarkCompactCollector::RecordLiveSlotsOnPage(Page* page) {
EvacuateRecordOnlyVisitor visitor(heap());
LiveObjectVisitor::VisitBlackObjectsNoFail(page, non_atomic_marking_state(),
&visitor,
LiveObjectVisitor::kKeepMarking);
}
template <class Visitor, typename MarkingState>
bool LiveObjectVisitor::VisitBlackObjects(MemoryChunk* chunk,
MarkingState* marking_state,
Visitor* visitor,
IterationMode iteration_mode,
HeapObject* failed_object) {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"LiveObjectVisitor::VisitBlackObjects");
for (auto object_and_size :
LiveObjectRange<kBlackObjects>(chunk, marking_state->bitmap(chunk))) {
HeapObject const object = object_and_size.first;
if (!visitor->Visit(object, object_and_size.second)) {
if (iteration_mode == kClearMarkbits) {
marking_state->bitmap(chunk)->ClearRange(
chunk->AddressToMarkbitIndex(chunk->area_start()),
chunk->AddressToMarkbitIndex(object.address()));
*failed_object = object;
}
return false;
}
}
if (iteration_mode == kClearMarkbits) {
marking_state->ClearLiveness(chunk);
}
return true;
}
template <class Visitor, typename MarkingState>
void LiveObjectVisitor::VisitBlackObjectsNoFail(MemoryChunk* chunk,
MarkingState* marking_state,
Visitor* visitor,
IterationMode iteration_mode) {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"LiveObjectVisitor::VisitBlackObjectsNoFail");
if (chunk->IsLargePage()) {
HeapObject object = reinterpret_cast<LargePage*>(chunk)->GetObject();
if (marking_state->IsBlack(object)) {
const bool success = visitor->Visit(object, object.Size());
USE(success);
DCHECK(success);
}
} else {
for (auto object_and_size :
LiveObjectRange<kBlackObjects>(chunk, marking_state->bitmap(chunk))) {
HeapObject const object = object_and_size.first;
DCHECK(marking_state->IsBlack(object));
const bool success = visitor->Visit(object, object_and_size.second);
USE(success);
DCHECK(success);
}
}
if (iteration_mode == kClearMarkbits) {
marking_state->ClearLiveness(chunk);
}
}
template <class Visitor, typename MarkingState>
void LiveObjectVisitor::VisitGreyObjectsNoFail(MemoryChunk* chunk,
MarkingState* marking_state,
Visitor* visitor,
IterationMode iteration_mode) {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"LiveObjectVisitor::VisitGreyObjectsNoFail");
if (chunk->IsLargePage()) {
HeapObject object = reinterpret_cast<LargePage*>(chunk)->GetObject();
if (marking_state->IsGrey(object)) {
const bool success = visitor->Visit(object, object.Size());
USE(success);
DCHECK(success);
}
} else {
for (auto object_and_size :
LiveObjectRange<kGreyObjects>(chunk, marking_state->bitmap(chunk))) {
HeapObject const object = object_and_size.first;
DCHECK(marking_state->IsGrey(object));
const bool success = visitor->Visit(object, object_and_size.second);
USE(success);
DCHECK(success);
}
}
if (iteration_mode == kClearMarkbits) {
marking_state->ClearLiveness(chunk);
}
}
template <typename MarkingState>
void LiveObjectVisitor::RecomputeLiveBytes(MemoryChunk* chunk,
MarkingState* marking_state) {
int new_live_size = 0;
for (auto object_and_size :
LiveObjectRange<kAllLiveObjects>(chunk, marking_state->bitmap(chunk))) {
new_live_size += object_and_size.second;
}
marking_state->SetLiveBytes(chunk, new_live_size);
}
void MarkCompactCollector::Evacuate() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE);
base::MutexGuard guard(heap()->relocation_mutex());
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE_PROLOGUE);
EvacuatePrologue();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE_COPY);
EvacuationScope evacuation_scope(this);
EvacuatePagesInParallel();
}
UpdatePointersAfterEvacuation();
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE_REBALANCE);
if (!heap()->new_space()->Rebalance()) {
heap()->FatalProcessOutOfMemory("NewSpace::Rebalance");
}
}
// Give pages that are queued to be freed back to the OS. Note that filtering
// slots only handles old space (for unboxed doubles), and thus map space can
// still contain stale pointers. We only free the chunks after pointer updates
// to still have access to page headers.
heap()->memory_allocator()->unmapper()->FreeQueuedChunks();
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE_CLEAN_UP);
for (Page* p : new_space_evacuation_pages_) {
if (p->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION)) {
p->ClearFlag(Page::PAGE_NEW_NEW_PROMOTION);
sweeper()->AddPageForIterability(p);
} else if (p->IsFlagSet(Page::PAGE_NEW_OLD_PROMOTION)) {
p->ClearFlag(Page::PAGE_NEW_OLD_PROMOTION);
DCHECK_EQ(OLD_SPACE, p->owner_identity());
sweeper()->AddPage(OLD_SPACE, p, Sweeper::REGULAR);
}
}
new_space_evacuation_pages_.clear();
for (Page* p : old_space_evacuation_pages_) {
if (p->IsFlagSet(Page::COMPACTION_WAS_ABORTED)) {
sweeper()->AddPage(p->owner_identity(), p, Sweeper::REGULAR);
p->ClearFlag(Page::COMPACTION_WAS_ABORTED);
}
}
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE_EPILOGUE);
EvacuateEpilogue();
}
#ifdef VERIFY_HEAP
if (FLAG_verify_heap && !sweeper()->sweeping_in_progress()) {
FullEvacuationVerifier verifier(heap());
verifier.Run();
}
#endif
}
class UpdatingItem : public ParallelWorkItem {
public:
virtual ~UpdatingItem() = default;
virtual void Process() = 0;
};
class PointersUpdatingJob : public v8::JobTask {
public:
explicit PointersUpdatingJob(
Isolate* isolate,
std::vector<std::unique_ptr<UpdatingItem>> updating_items, int slots,
GCTracer::Scope::ScopeId scope,
GCTracer::BackgroundScope::ScopeId background_scope)
: updating_items_(std::move(updating_items)),
remaining_updating_items_(updating_items_.size()),
generator_(updating_items_.size()),
slots_(slots),
tracer_(isolate->heap()->tracer()),
scope_(scope),
background_scope_(background_scope) {}
void Run(JobDelegate* delegate) override {
if (delegate->IsJoiningThread()) {
TRACE_GC(tracer_, scope_);
UpdatePointers(delegate);
} else {
TRACE_BACKGROUND_GC(tracer_, background_scope_);
UpdatePointers(delegate);
}
}
void UpdatePointers(JobDelegate* delegate) {
while (remaining_updating_items_.load(std::memory_order_relaxed) > 0) {
base::Optional<size_t> index = generator_.GetNext();
if (!index) return;
for (size_t i = *index; i < updating_items_.size(); ++i) {
auto& work_item = updating_items_[i];
if (!work_item->TryAcquire()) break;
work_item->Process();
if (remaining_updating_items_.fetch_sub(1, std::memory_order_relaxed) <=
1) {
return;
}
}
}
}
size_t GetMaxConcurrency(size_t worker_count) const override {
size_t items = remaining_updating_items_.load(std::memory_order_relaxed);
if (!FLAG_parallel_pointer_update) return items > 0;
const size_t kMaxPointerUpdateTasks = 8;
const size_t kSlotsPerTask = 600;
size_t wanted_tasks = items;
// Limit the number of update tasks as task creation often dominates the
// actual work that is being done.
if (slots_ >= 0) {
// Round up to ensure enough workers for all items.
wanted_tasks =
std::min<size_t>(items, (slots_ + kSlotsPerTask - 1) / kSlotsPerTask);
}
return std::min<size_t>(kMaxPointerUpdateTasks, wanted_tasks);
}
private:
std::vector<std::unique_ptr<UpdatingItem>> updating_items_;
std::atomic<size_t> remaining_updating_items_{0};
IndexGenerator generator_;
const int slots_;
GCTracer* tracer_;
GCTracer::Scope::ScopeId scope_;
GCTracer::BackgroundScope::ScopeId background_scope_;
};
template <typename MarkingState>
class ToSpaceUpdatingItem : public UpdatingItem {
public:
explicit ToSpaceUpdatingItem(MemoryChunk* chunk, Address start, Address end,
MarkingState* marking_state)
: chunk_(chunk),
start_(start),
end_(end),
marking_state_(marking_state) {}
~ToSpaceUpdatingItem() override = default;
void Process() override {
if (chunk_->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION)) {
// New->new promoted pages contain garbage so they require iteration using
// markbits.
ProcessVisitLive();
} else {
ProcessVisitAll();
}
}
private:
void ProcessVisitAll() {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"ToSpaceUpdatingItem::ProcessVisitAll");
PointersUpdatingVisitor visitor(
GetIsolateForPtrComprFromOnHeapAddress(start_));
for (Address cur = start_; cur < end_;) {
HeapObject object = HeapObject::FromAddress(cur);
Map map = object.map();
int size = object.SizeFromMap(map);
object.IterateBodyFast(map, size, &visitor);
cur += size;
}
}
void ProcessVisitLive() {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"ToSpaceUpdatingItem::ProcessVisitLive");
// For young generation evacuations we want to visit grey objects, for
// full MC, we need to visit black objects.
PointersUpdatingVisitor visitor(
GetIsolateForPtrComprFromOnHeapAddress(start_));
for (auto object_and_size : LiveObjectRange<kAllLiveObjects>(
chunk_, marking_state_->bitmap(chunk_))) {
object_and_size.first.IterateBodyFast(&visitor);
}
}
MemoryChunk* chunk_;
Address start_;
Address end_;
MarkingState* marking_state_;
};
template <typename MarkingState, GarbageCollector collector>
class RememberedSetUpdatingItem : public UpdatingItem {
public:
explicit RememberedSetUpdatingItem(Heap* heap, MarkingState* marking_state,
MemoryChunk* chunk,
RememberedSetUpdatingMode updating_mode)
: heap_(heap),
marking_state_(marking_state),
chunk_(chunk),
updating_mode_(updating_mode) {}
~RememberedSetUpdatingItem() override = default;
void Process() override {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"RememberedSetUpdatingItem::Process");
base::MutexGuard guard(chunk_->mutex());
CodePageMemoryModificationScope memory_modification_scope(chunk_);
UpdateUntypedPointers();
UpdateTypedPointers();
}
private:
template <typename TSlot>
inline SlotCallbackResult CheckAndUpdateOldToNewSlot(TSlot slot) {
static_assert(
std::is_same<TSlot, FullMaybeObjectSlot>::value ||
std::is_same<TSlot, MaybeObjectSlot>::value,
"Only FullMaybeObjectSlot and MaybeObjectSlot are expected here");
using THeapObjectSlot = typename TSlot::THeapObjectSlot;
HeapObject heap_object;
if (!(*slot).GetHeapObject(&heap_object)) {
return REMOVE_SLOT;
}
if (Heap::InFromPage(heap_object)) {
MapWord map_word = heap_object.map_word();
if (map_word.IsForwardingAddress()) {
HeapObjectReference::Update(THeapObjectSlot(slot),
map_word.ToForwardingAddress());
}
bool success = (*slot).GetHeapObject(&heap_object);
USE(success);
DCHECK(success);
// If the object was in from space before and is after executing the
// callback in to space, the object is still live.
// Unfortunately, we do not know about the slot. It could be in a
// just freed free space object.
if (Heap::InToPage(heap_object)) {
return KEEP_SLOT;
}
} else if (Heap::InToPage(heap_object)) {
// Slots can point to "to" space if the page has been moved, or if the
// slot has been recorded multiple times in the remembered set, or
// if the slot was already updated during old->old updating.
// In case the page has been moved, check markbits to determine liveness
// of the slot. In the other case, the slot can just be kept.
if (Page::FromHeapObject(heap_object)
->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION)) {
// IsBlackOrGrey is required because objects are marked as grey for
// the young generation collector while they are black for the full
// MC.);
if (marking_state_->IsBlackOrGrey(heap_object)) {
return KEEP_SLOT;
} else {
return REMOVE_SLOT;
}
}
return KEEP_SLOT;
} else {
DCHECK(!Heap::InYoungGeneration(heap_object));
}
return REMOVE_SLOT;
}
void UpdateUntypedPointers() {
if (chunk_->slot_set<OLD_TO_NEW, AccessMode::NON_ATOMIC>() != nullptr) {
DCHECK_IMPLIES(
collector == MARK_COMPACTOR,
chunk_->SweepingDone() &&
chunk_->sweeping_slot_set<AccessMode::NON_ATOMIC>() == nullptr);
InvalidatedSlotsFilter filter = InvalidatedSlotsFilter::OldToNew(chunk_);
int slots = RememberedSet<OLD_TO_NEW>::Iterate(
chunk_,
[this, &filter](MaybeObjectSlot slot) {
if (!filter.IsValid(slot.address())) return REMOVE_SLOT;
return CheckAndUpdateOldToNewSlot(slot);
},
SlotSet::FREE_EMPTY_BUCKETS);
DCHECK_IMPLIES(
collector == MARK_COMPACTOR && FLAG_always_promote_young_mc,
slots == 0);
if (slots == 0) {
chunk_->ReleaseSlotSet<OLD_TO_NEW>();
}
}
if (chunk_->sweeping_slot_set<AccessMode::NON_ATOMIC>()) {
DCHECK_IMPLIES(
collector == MARK_COMPACTOR,
!chunk_->SweepingDone() &&
(chunk_->slot_set<OLD_TO_NEW, AccessMode::NON_ATOMIC>()) ==
nullptr);
DCHECK(!chunk_->IsLargePage());
InvalidatedSlotsFilter filter = InvalidatedSlotsFilter::OldToNew(chunk_);
int slots = RememberedSetSweeping::Iterate(
chunk_,
[this, &filter](MaybeObjectSlot slot) {
if (!filter.IsValid(slot.address())) return REMOVE_SLOT;
return CheckAndUpdateOldToNewSlot(slot);
},
SlotSet::FREE_EMPTY_BUCKETS);
DCHECK_IMPLIES(
collector == MARK_COMPACTOR && FLAG_always_promote_young_mc,
slots == 0);
if (slots == 0) {
chunk_->ReleaseSweepingSlotSet();
}
}
if (chunk_->invalidated_slots<OLD_TO_NEW>() != nullptr) {
// The invalidated slots are not needed after old-to-new slots were
// processed.
chunk_->ReleaseInvalidatedSlots<OLD_TO_NEW>();
}
if ((updating_mode_ == RememberedSetUpdatingMode::ALL) &&
(chunk_->slot_set<OLD_TO_OLD, AccessMode::NON_ATOMIC>() != nullptr)) {
InvalidatedSlotsFilter filter = InvalidatedSlotsFilter::OldToOld(chunk_);
IsolateRoot isolate = heap_->isolate();
RememberedSet<OLD_TO_OLD>::Iterate(
chunk_,
[&filter, isolate](MaybeObjectSlot slot) {
if (!filter.IsValid(slot.address())) return REMOVE_SLOT;
return UpdateSlot<AccessMode::NON_ATOMIC>(isolate, slot);
},
SlotSet::FREE_EMPTY_BUCKETS);
chunk_->ReleaseSlotSet<OLD_TO_OLD>();
}
if ((updating_mode_ == RememberedSetUpdatingMode::ALL) &&
chunk_->invalidated_slots<OLD_TO_OLD>() != nullptr) {
// The invalidated slots are not needed after old-to-old slots were
// processsed.
chunk_->ReleaseInvalidatedSlots<OLD_TO_OLD>();
}
}
void UpdateTypedPointers() {
if (chunk_->typed_slot_set<OLD_TO_NEW, AccessMode::NON_ATOMIC>() !=
nullptr) {
CHECK_NE(chunk_->owner(), heap_->map_space());
const auto check_and_update_old_to_new_slot_fn =
[this](FullMaybeObjectSlot slot) {
return CheckAndUpdateOldToNewSlot(slot);
};
RememberedSet<OLD_TO_NEW>::IterateTyped(
chunk_, [=](SlotType slot_type, Address slot) {
return UpdateTypedSlotHelper::UpdateTypedSlot(
heap_, slot_type, slot, check_and_update_old_to_new_slot_fn);
});
}
if ((updating_mode_ == RememberedSetUpdatingMode::ALL) &&
(chunk_->typed_slot_set<OLD_TO_OLD, AccessMode::NON_ATOMIC>() !=
nullptr)) {
CHECK_NE(chunk_->owner(), heap_->map_space());
RememberedSet<OLD_TO_OLD>::IterateTyped(chunk_, [=](SlotType slot_type,
Address slot) {
// Using UpdateStrongSlot is OK here, because there are no weak
// typed slots.
IsolateRoot isolate = heap_->isolate();
return UpdateTypedSlotHelper::UpdateTypedSlot(
heap_, slot_type, slot, [isolate](FullMaybeObjectSlot slot) {
return UpdateStrongSlot<AccessMode::NON_ATOMIC>(isolate, slot);
});
});
}
}
Heap* heap_;
MarkingState* marking_state_;
MemoryChunk* chunk_;
RememberedSetUpdatingMode updating_mode_;
};
std::unique_ptr<UpdatingItem> MarkCompactCollector::CreateToSpaceUpdatingItem(
MemoryChunk* chunk, Address start, Address end) {
return std::make_unique<ToSpaceUpdatingItem<NonAtomicMarkingState>>(
chunk, start, end, non_atomic_marking_state());
}
std::unique_ptr<UpdatingItem>
MarkCompactCollector::CreateRememberedSetUpdatingItem(
MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) {
return std::make_unique<
RememberedSetUpdatingItem<NonAtomicMarkingState, MARK_COMPACTOR>>(
heap(), non_atomic_marking_state(), chunk, updating_mode);
}
int MarkCompactCollectorBase::CollectToSpaceUpdatingItems(
std::vector<std::unique_ptr<UpdatingItem>>* items) {
// Seed to space pages.
const Address space_start = heap()->new_space()->first_allocatable_address();
const Address space_end = heap()->new_space()->top();
int pages = 0;
for (Page* page : PageRange(space_start, space_end)) {
Address start =
page->Contains(space_start) ? space_start : page->area_start();
Address end = page->Contains(space_end) ? space_end : page->area_end();
items->emplace_back(CreateToSpaceUpdatingItem(page, start, end));
pages++;
}
return pages;
}
template <typename IterateableSpace>
int MarkCompactCollectorBase::CollectRememberedSetUpdatingItems(
std::vector<std::unique_ptr<UpdatingItem>>* items, IterateableSpace* space,
RememberedSetUpdatingMode mode) {
int pages = 0;
for (MemoryChunk* chunk : *space) {
const bool contains_old_to_old_slots =
chunk->slot_set<OLD_TO_OLD>() != nullptr ||
chunk->typed_slot_set<OLD_TO_OLD>() != nullptr;
const bool contains_old_to_new_slots =
chunk->slot_set<OLD_TO_NEW>() != nullptr ||
chunk->typed_slot_set<OLD_TO_NEW>() != nullptr;
const bool contains_old_to_new_sweeping_slots =
chunk->sweeping_slot_set() != nullptr;
const bool contains_old_to_old_invalidated_slots =
chunk->invalidated_slots<OLD_TO_OLD>() != nullptr;
const bool contains_old_to_new_invalidated_slots =
chunk->invalidated_slots<OLD_TO_NEW>() != nullptr;
if (!contains_old_to_new_slots && !contains_old_to_new_sweeping_slots &&
!contains_old_to_old_slots && !contains_old_to_old_invalidated_slots &&
!contains_old_to_new_invalidated_slots)
continue;
if (mode == RememberedSetUpdatingMode::ALL || contains_old_to_new_slots ||
contains_old_to_new_sweeping_slots ||
contains_old_to_old_invalidated_slots ||
contains_old_to_new_invalidated_slots) {
items->emplace_back(CreateRememberedSetUpdatingItem(chunk, mode));
pages++;
}
}
return pages;
}
class EphemeronTableUpdatingItem : public UpdatingItem {
public:
enum EvacuationState { kRegular, kAborted };
explicit EphemeronTableUpdatingItem(Heap* heap) : heap_(heap) {}
~EphemeronTableUpdatingItem() override = default;
void Process() override {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"EphemeronTableUpdatingItem::Process");
for (auto it = heap_->ephemeron_remembered_set_.begin();
it != heap_->ephemeron_remembered_set_.end();) {
EphemeronHashTable table = it->first;
auto& indices = it->second;
if (table.map_word().IsForwardingAddress()) {
// The table has moved, and RecordMigratedSlotVisitor::VisitEphemeron
// inserts entries for the moved table into ephemeron_remembered_set_.
it = heap_->ephemeron_remembered_set_.erase(it);
continue;
}
DCHECK(table.map().IsMap());
DCHECK(table.Object::IsEphemeronHashTable());
for (auto iti = indices.begin(); iti != indices.end();) {
// EphemeronHashTable keys must be heap objects.
HeapObjectSlot key_slot(table.RawFieldOfElementAt(
EphemeronHashTable::EntryToIndex(InternalIndex(*iti))));
HeapObject key = key_slot.ToHeapObject();
MapWord map_word = key.map_word();
if (map_word.IsForwardingAddress()) {
key = map_word.ToForwardingAddress();
key_slot.StoreHeapObject(key);
}
if (!heap_->InYoungGeneration(key)) {
iti = indices.erase(iti);
} else {
++iti;
}
}
if (indices.size() == 0) {
it = heap_->ephemeron_remembered_set_.erase(it);
} else {
++it;
}
}
}
private:
Heap* const heap_;
};
void MarkCompactCollector::UpdatePointersAfterEvacuation() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS);
PointersUpdatingVisitor updating_visitor(isolate());
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_TO_NEW_ROOTS);
// The external string table is updated at the end.
heap_->IterateRoots(&updating_visitor, base::EnumSet<SkipRoot>{
SkipRoot::kExternalStringTable});
}
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_SLOTS_MAIN);
std::vector<std::unique_ptr<UpdatingItem>> updating_items;
CollectRememberedSetUpdatingItems(&updating_items, heap()->old_space(),
RememberedSetUpdatingMode::ALL);
CollectRememberedSetUpdatingItems(&updating_items, heap()->code_space(),
RememberedSetUpdatingMode::ALL);
CollectRememberedSetUpdatingItems(&updating_items, heap()->lo_space(),
RememberedSetUpdatingMode::ALL);
CollectRememberedSetUpdatingItems(&updating_items, heap()->code_lo_space(),
RememberedSetUpdatingMode::ALL);
CollectToSpaceUpdatingItems(&updating_items);
updating_items.push_back(
std::make_unique<EphemeronTableUpdatingItem>(heap()));
V8::GetCurrentPlatform()
->PostJob(v8::TaskPriority::kUserBlocking,
std::make_unique<PointersUpdatingJob>(
isolate(), std::move(updating_items), old_to_new_slots_,
GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_PARALLEL,
GCTracer::BackgroundScope::
MC_BACKGROUND_EVACUATE_UPDATE_POINTERS))
->Join();
}
{
// - Update pointers in map space in a separate phase to avoid data races
// with Map->LayoutDescriptor edge.
// - Update array buffer trackers in the second phase to have access to
// byte length which is potentially a HeapNumber.
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_SLOTS_MAP_SPACE);
std::vector<std::unique_ptr<UpdatingItem>> updating_items;
CollectRememberedSetUpdatingItems(&updating_items, heap()->map_space(),
RememberedSetUpdatingMode::ALL);
if (!updating_items.empty()) {
V8::GetCurrentPlatform()
->PostJob(v8::TaskPriority::kUserBlocking,
std::make_unique<PointersUpdatingJob>(
isolate(), std::move(updating_items), old_to_new_slots_,
GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_PARALLEL,
GCTracer::BackgroundScope::
MC_BACKGROUND_EVACUATE_UPDATE_POINTERS))
->Join();
}
}
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_WEAK);
// Update pointers from external string table.
heap_->UpdateReferencesInExternalStringTable(
&UpdateReferenceInExternalStringTableEntry);
EvacuationWeakObjectRetainer evacuation_object_retainer;
heap()->ProcessWeakListRoots(&evacuation_object_retainer);
}
}
void MarkCompactCollector::ReportAbortedEvacuationCandidate(
HeapObject failed_object, MemoryChunk* chunk) {
base::MutexGuard guard(&mutex_);
aborted_evacuation_candidates_.push_back(
std::make_pair(failed_object, static_cast<Page*>(chunk)));
}
void MarkCompactCollector::PostProcessEvacuationCandidates() {
for (auto object_and_page : aborted_evacuation_candidates_) {
HeapObject failed_object = object_and_page.first;
Page* page = object_and_page.second;
page->SetFlag(Page::COMPACTION_WAS_ABORTED);
// Aborted compaction page. We have to record slots here, since we
// might not have recorded them in first place.
// Remove outdated slots.
RememberedSetSweeping::RemoveRange(page, page->address(),
failed_object.address(),
SlotSet::FREE_EMPTY_BUCKETS);
RememberedSet<OLD_TO_NEW>::RemoveRange(page, page->address(),
failed_object.address(),
SlotSet::FREE_EMPTY_BUCKETS);
RememberedSet<OLD_TO_NEW>::RemoveRangeTyped(page, page->address(),
failed_object.address());
// Remove invalidated slots.
if (failed_object.address() > page->area_start()) {
InvalidatedSlotsCleanup old_to_new_cleanup =
InvalidatedSlotsCleanup::OldToNew(page);
old_to_new_cleanup.Free(page->area_start(), failed_object.address());
}
// Recompute live bytes.
LiveObjectVisitor::RecomputeLiveBytes(page, non_atomic_marking_state());
// Re-record slots.
EvacuateRecordOnlyVisitor record_visitor(heap());
LiveObjectVisitor::VisitBlackObjectsNoFail(page, non_atomic_marking_state(),
&record_visitor,
LiveObjectVisitor::kKeepMarking);
// Array buffers will be processed during pointer updating.
}
const int aborted_pages =
static_cast<int>(aborted_evacuation_candidates_.size());
int aborted_pages_verified = 0;
for (Page* p : old_space_evacuation_pages_) {
if (p->IsFlagSet(Page::COMPACTION_WAS_ABORTED)) {
// After clearing the evacuation candidate flag the page is again in a
// regular state.
p->ClearEvacuationCandidate();
aborted_pages_verified++;
} else {
DCHECK(p->IsEvacuationCandidate());
DCHECK(p->SweepingDone());
p->owner()->memory_chunk_list().Remove(p);
}
}
DCHECK_EQ(aborted_pages_verified, aborted_pages);
if (FLAG_trace_evacuation && (aborted_pages > 0)) {
PrintIsolate(isolate(), "%8.0f ms: evacuation: aborted=%d\n",
isolate()->time_millis_since_init(), aborted_pages);
}
}
void MarkCompactCollector::ReleaseEvacuationCandidates() {
for (Page* p : old_space_evacuation_pages_) {
if (!p->IsEvacuationCandidate()) continue;
PagedSpace* space = static_cast<PagedSpace*>(p->owner());
non_atomic_marking_state()->SetLiveBytes(p, 0);
CHECK(p->SweepingDone());
space->ReleasePage(p);
}
old_space_evacuation_pages_.clear();
compacting_ = false;
}
void MarkCompactCollector::StartSweepSpace(PagedSpace* space) {
space->ClearAllocatorState();
int will_be_swept = 0;
bool unused_page_present = false;
// Loop needs to support deletion if live bytes == 0 for a page.
for (auto it = space->begin(); it != space->end();) {
Page* p = *(it++);
DCHECK(p->SweepingDone());
if (p->IsEvacuationCandidate()) {
// Will be processed in Evacuate.
DCHECK(!evacuation_candidates_.empty());
continue;
}
// One unused page is kept, all further are released before sweeping them.
if (non_atomic_marking_state()->live_bytes(p) == 0) {
if (unused_page_present) {
if (FLAG_gc_verbose) {
PrintIsolate(isolate(), "sweeping: released page: %p",
static_cast<void*>(p));
}
space->memory_chunk_list().Remove(p);
space->ReleasePage(p);
continue;
}
unused_page_present = true;
}
sweeper()->AddPage(space->identity(), p, Sweeper::REGULAR);
will_be_swept++;
}
if (FLAG_gc_verbose) {
PrintIsolate(isolate(), "sweeping: space=%s initialized_for_sweeping=%d",
space->name(), will_be_swept);
}
}
void MarkCompactCollector::StartSweepSpaces() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_SWEEP);
#ifdef DEBUG
state_ = SWEEP_SPACES;
#endif
{
{
GCTracer::Scope sweep_scope(heap()->tracer(),
GCTracer::Scope::MC_SWEEP_OLD);
StartSweepSpace(heap()->old_space());
}
{
GCTracer::Scope sweep_scope(heap()->tracer(),
GCTracer::Scope::MC_SWEEP_CODE);
StartSweepSpace(heap()->code_space());
}
{
GCTracer::Scope sweep_scope(heap()->tracer(),
GCTracer::Scope::MC_SWEEP_MAP);
StartSweepSpace(heap()->map_space());
}
sweeper()->StartSweeping();
}
}
#ifdef ENABLE_MINOR_MC
namespace {
#ifdef VERIFY_HEAP
class YoungGenerationMarkingVerifier : public MarkingVerifier {
public:
explicit YoungGenerationMarkingVerifier(Heap* heap)
: MarkingVerifier(heap),
marking_state_(
heap->minor_mark_compact_collector()->non_atomic_marking_state()) {}
ConcurrentBitmap<AccessMode::NON_ATOMIC>* bitmap(
const MemoryChunk* chunk) override {
return marking_state_->bitmap(chunk);
}
bool IsMarked(HeapObject object) override {
return marking_state_->IsGrey(object);
}
bool IsBlackOrGrey(HeapObject object) override {
return marking_state_->IsBlackOrGrey(object);
}
void Run() override {
VerifyRoots();
VerifyMarking(heap_->new_space());
}
protected:
void VerifyPointers(ObjectSlot start, ObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VerifyPointers(MaybeObjectSlot start, MaybeObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
VerifyHeapObjectImpl(target);
}
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
VerifyHeapObjectImpl(rinfo->target_object());
}
void VerifyRootPointers(FullObjectSlot start, FullObjectSlot end) override {
VerifyPointersImpl(start, end);
}
private:
V8_INLINE void VerifyHeapObjectImpl(HeapObject heap_object) {
CHECK_IMPLIES(Heap::InYoungGeneration(heap_object), IsMarked(heap_object));
}
template <typename TSlot>
V8_INLINE void VerifyPointersImpl(TSlot start, TSlot end) {
for (TSlot slot = start; slot < end; ++slot) {
typename TSlot::TObject object = *slot;
HeapObject heap_object;
// Minor MC treats weak references as strong.
if (object.GetHeapObject(&heap_object)) {
VerifyHeapObjectImpl(heap_object);
}
}
}
MinorMarkCompactCollector::NonAtomicMarkingState* marking_state_;
};
class YoungGenerationEvacuationVerifier : public EvacuationVerifier {
public:
explicit YoungGenerationEvacuationVerifier(Heap* heap)
: EvacuationVerifier(heap) {}
void Run() override {
VerifyRoots();
VerifyEvacuation(heap_->new_space());
VerifyEvacuation(heap_->old_space());
VerifyEvacuation(heap_->code_space());
VerifyEvacuation(heap_->map_space());
}
protected:
V8_INLINE void VerifyHeapObjectImpl(HeapObject heap_object) {
CHECK_IMPLIES(Heap::InYoungGeneration(heap_object),
Heap::InToPage(heap_object));
}
template <typename TSlot>
void VerifyPointersImpl(TSlot start, TSlot end) {
for (TSlot current = start; current < end; ++current) {
typename TSlot::TObject object = *current;
HeapObject heap_object;
if (object.GetHeapObject(&heap_object)) {
VerifyHeapObjectImpl(heap_object);
}
}
}
void VerifyPointers(ObjectSlot start, ObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VerifyPointers(MaybeObjectSlot start, MaybeObjectSlot end) override {
VerifyPointersImpl(start, end);
}
void VisitCodeTarget(Code host, RelocInfo* rinfo) override {
Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
VerifyHeapObjectImpl(target);
}
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) override {
VerifyHeapObjectImpl(rinfo->target_object());
}
void VerifyRootPointers(FullObjectSlot start, FullObjectSlot end) override {
VerifyPointersImpl(start, end);
}
};
#endif // VERIFY_HEAP
bool IsUnmarkedObjectForYoungGeneration(Heap* heap, FullObjectSlot p) {
DCHECK_IMPLIES(Heap::InYoungGeneration(*p), Heap::InToPage(*p));
return Heap::InYoungGeneration(*p) && !heap->minor_mark_compact_collector()
->non_atomic_marking_state()
->IsGrey(HeapObject::cast(*p));
}
} // namespace
class YoungGenerationMarkingVisitor final
: public NewSpaceVisitor<YoungGenerationMarkingVisitor> {
public:
YoungGenerationMarkingVisitor(
MinorMarkCompactCollector::MarkingState* marking_state,
MinorMarkCompactCollector::MarkingWorklist* global_worklist, int task_id)
: worklist_(global_worklist, task_id), marking_state_(marking_state) {}
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 VisitPointer(HeapObject host, ObjectSlot slot) final {
VisitPointerImpl(host, slot);
}
V8_INLINE void VisitPointer(HeapObject host, MaybeObjectSlot slot) final {
VisitPointerImpl(host, slot);
}
V8_INLINE void VisitCodeTarget(Code host, RelocInfo* rinfo) final {
// Code objects are not expected in new space.
UNREACHABLE();
}
V8_INLINE void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final {
// Code objects are not expected in new space.
UNREACHABLE();
}
V8_INLINE int VisitJSArrayBuffer(Map map, JSArrayBuffer object) {
object.YoungMarkExtension();
int size = JSArrayBuffer::BodyDescriptor::SizeOf(map, object);
JSArrayBuffer::BodyDescriptor::IterateBody(map, object, size, this);
return size;
}
private:
template <typename TSlot>
V8_INLINE void VisitPointersImpl(HeapObject host, TSlot start, TSlot end) {
for (TSlot slot = start; slot < end; ++slot) {
VisitPointer(host, slot);
}
}
template <typename TSlot>
V8_INLINE void VisitPointerImpl(HeapObject host, TSlot slot) {
typename TSlot::TObject target = *slot;
if (Heap::InYoungGeneration(target)) {
// Treat weak references as strong.
// TODO(marja): Proper weakness handling for minor-mcs.
HeapObject target_object = target.GetHeapObject();
MarkObjectViaMarkingWorklist(target_object);
}
}
inline void MarkObjectViaMarkingWorklist(HeapObject object) {
if (marking_state_->WhiteToGrey(object)) {
// Marking deque overflow is unsupported for the young generation.
CHECK(worklist_.Push(object));
}
}
MinorMarkCompactCollector::MarkingWorklist::View worklist_;
MinorMarkCompactCollector::MarkingState* marking_state_;
};
void MinorMarkCompactCollector::SetUp() {}
void MinorMarkCompactCollector::TearDown() {}
MinorMarkCompactCollector::MinorMarkCompactCollector(Heap* heap)
: MarkCompactCollectorBase(heap),
worklist_(new MinorMarkCompactCollector::MarkingWorklist()),
main_marking_visitor_(new YoungGenerationMarkingVisitor(
marking_state(), worklist_, kMainMarker)),
page_parallel_job_semaphore_(0) {
static_assert(
kNumMarkers <= MinorMarkCompactCollector::MarkingWorklist::kMaxNumTasks,
"more marker tasks than marking deque can handle");
}
MinorMarkCompactCollector::~MinorMarkCompactCollector() {
delete worklist_;
delete main_marking_visitor_;
}
void MinorMarkCompactCollector::CleanupSweepToIteratePages() {
for (Page* p : sweep_to_iterate_pages_) {
if (p->IsFlagSet(Page::SWEEP_TO_ITERATE)) {
p->ClearFlag(Page::SWEEP_TO_ITERATE);
non_atomic_marking_state()->ClearLiveness(p);
}
}
sweep_to_iterate_pages_.clear();
}
void MinorMarkCompactCollector::SweepArrayBufferExtensions() {
heap_->array_buffer_sweeper()->RequestSweepYoung();
}
class YoungGenerationMigrationObserver final : public MigrationObserver {
public:
YoungGenerationMigrationObserver(Heap* heap,
MarkCompactCollector* mark_compact_collector)
: MigrationObserver(heap),
mark_compact_collector_(mark_compact_collector) {}
inline void Move(AllocationSpace dest, HeapObject src, HeapObject dst,
int size) final {
// Migrate color to old generation marking in case the object survived young
// generation garbage collection.
if (heap_->incremental_marking()->IsMarking()) {
DCHECK(
heap_->incremental_marking()->atomic_marking_state()->IsWhite(dst));
heap_->incremental_marking()->TransferColor(src, dst);
}
}
protected:
base::Mutex mutex_;
MarkCompactCollector* mark_compact_collector_;
};
class YoungGenerationRecordMigratedSlotVisitor final
: public RecordMigratedSlotVisitor {
public:
explicit YoungGenerationRecordMigratedSlotVisitor(
MarkCompactCollector* collector)
: RecordMigratedSlotVisitor(collector, nullptr) {}
void VisitCodeTarget(Code host, RelocInfo* rinfo) final { UNREACHABLE(); }
void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final {
UNREACHABLE();
}
void MarkArrayBufferExtensionPromoted(HeapObject object) final {
if (!object.IsJSArrayBuffer()) return;
JSArrayBuffer::cast(object).YoungMarkExtensionPromoted();
}
private:
// Only record slots for host objects that are considered as live by the full
// collector.
inline bool IsLive(HeapObject object) {
return collector_->non_atomic_marking_state()->IsBlack(object);
}
inline void RecordMigratedSlot(HeapObject host, MaybeObject value,
Address slot) final {
if (value->IsStrongOrWeak()) {
BasicMemoryChunk* p = BasicMemoryChunk::FromAddress(value.ptr());
if (p->InYoungGeneration()) {
DCHECK_IMPLIES(
p->IsToPage(),
p->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION) || p->IsLargePage());
MemoryChunk* chunk = MemoryChunk::FromHeapObject(host);
DCHECK(chunk->SweepingDone());
RememberedSet<OLD_TO_NEW>::Insert<AccessMode::NON_ATOMIC>(chunk, slot);
} else if (p->IsEvacuationCandidate() && IsLive(host)) {
RememberedSet<OLD_TO_OLD>::Insert<AccessMode::NON_ATOMIC>(
MemoryChunk::FromHeapObject(host), slot);
}
}
}
};
void MinorMarkCompactCollector::UpdatePointersAfterEvacuation() {
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MINOR_MC_EVACUATE_UPDATE_POINTERS);
PointersUpdatingVisitor updating_visitor(isolate());
std::vector<std::unique_ptr<UpdatingItem>> updating_items;
// Create batches of global handles.
CollectToSpaceUpdatingItems(&updating_items);
CollectRememberedSetUpdatingItems(&updating_items, heap()->old_space(),
RememberedSetUpdatingMode::OLD_TO_NEW_ONLY);
CollectRememberedSetUpdatingItems(&updating_items, heap()->code_space(),
RememberedSetUpdatingMode::OLD_TO_NEW_ONLY);
CollectRememberedSetUpdatingItems(&updating_items, heap()->map_space(),
RememberedSetUpdatingMode::OLD_TO_NEW_ONLY);
CollectRememberedSetUpdatingItems(&updating_items, heap()->lo_space(),
RememberedSetUpdatingMode::OLD_TO_NEW_ONLY);
CollectRememberedSetUpdatingItems(&updating_items, heap()->code_lo_space(),
RememberedSetUpdatingMode::OLD_TO_NEW_ONLY);
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MINOR_MC_EVACUATE_UPDATE_POINTERS_TO_NEW_ROOTS);
heap()->IterateRoots(&updating_visitor,
base::EnumSet<SkipRoot>{SkipRoot::kExternalStringTable,
SkipRoot::kOldGeneration});
}
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MINOR_MC_EVACUATE_UPDATE_POINTERS_SLOTS);
V8::GetCurrentPlatform()
->PostJob(
v8::TaskPriority::kUserBlocking,
std::make_unique<PointersUpdatingJob>(
isolate(), std::move(updating_items), old_to_new_slots_,
GCTracer::Scope::MINOR_MC_EVACUATE_UPDATE_POINTERS_PARALLEL,
GCTracer::BackgroundScope::
MINOR_MC_BACKGROUND_EVACUATE_UPDATE_POINTERS))
->Join();
}
{
TRACE_GC(heap()->tracer(),
GCTracer::Scope::MINOR_MC_EVACUATE_UPDATE_POINTERS_WEAK);
EvacuationWeakObjectRetainer evacuation_object_retainer;
heap()->ProcessWeakListRoots(&evacuation_object_retainer);
// Update pointers from external string table.
heap()->UpdateYoungReferencesInExternalStringTable(
&UpdateReferenceInExternalStringTableEntry);
}
}
class MinorMarkCompactCollector::RootMarkingVisitor : public RootVisitor {
public:
explicit RootMarkingVisitor(MinorMarkCompactCollector* collector)
: collector_(collector) {}
void VisitRootPointer(Root root, const char* description,
FullObjectSlot p) final {
MarkObjectByPointer(p);
}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) final {
for (FullObjectSlot p = start; p < end; ++p) {
MarkObjectByPointer(p);
}
}
private:
V8_INLINE void MarkObjectByPointer(FullObjectSlot p) {
if (!(*p).IsHeapObject()) return;
collector_->MarkRootObject(HeapObject::cast(*p));
}
MinorMarkCompactCollector* const collector_;
};
void MinorMarkCompactCollector::CollectGarbage() {
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_SWEEPING);
heap()->mark_compact_collector()->sweeper()->EnsureIterabilityCompleted();
CleanupSweepToIteratePages();
}
heap()->array_buffer_sweeper()->EnsureFinished();
MarkLiveObjects();
ClearNonLiveReferences();
#ifdef VERIFY_HEAP
if (FLAG_verify_heap) {
YoungGenerationMarkingVerifier verifier(heap());
verifier.Run();
}
#endif // VERIFY_HEAP
Evacuate();
#ifdef VERIFY_HEAP
if (FLAG_verify_heap) {
YoungGenerationEvacuationVerifier verifier(heap());
verifier.Run();
}
#endif // VERIFY_HEAP
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_MARKING_DEQUE);
heap()->incremental_marking()->UpdateMarkingWorklistAfterScavenge();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_RESET_LIVENESS);
for (Page* p :
PageRange(heap()->new_space()->from_space().first_page(), nullptr)) {
DCHECK(!p->IsFlagSet(Page::SWEEP_TO_ITERATE));
non_atomic_marking_state()->ClearLiveness(p);
if (FLAG_concurrent_marking) {
// Ensure that concurrent marker does not track pages that are
// going to be unmapped.
heap()->concurrent_marking()->ClearMemoryChunkData(p);
}
}
// Since we promote all surviving large objects immediatelly, all remaining
// large objects must be dead.
// TODO(ulan): Don't free all as soon as we have an intermediate generation.
heap()->new_lo_space()->FreeDeadObjects([](HeapObject) { return true; });
}
SweepArrayBufferExtensions();
}
void MinorMarkCompactCollector::MakeIterable(
Page* p, MarkingTreatmentMode marking_mode,
FreeSpaceTreatmentMode free_space_mode) {
CHECK(!p->IsLargePage());
// We have to clear the full collectors markbits for the areas that we
// remove here.
MarkCompactCollector* full_collector = heap()->mark_compact_collector();
Address free_start = p->area_start();
for (auto object_and_size :
LiveObjectRange<kGreyObjects>(p, marking_state()->bitmap(p))) {
HeapObject const object = object_and_size.first;
DCHECK(non_atomic_marking_state()->IsGrey(object));
Address free_end = object.address();
if (free_end != free_start) {
CHECK_GT(free_end, free_start);
size_t size = static_cast<size_t>(free_end - free_start);
full_collector->non_atomic_marking_state()->bitmap(p)->ClearRange(
p->AddressToMarkbitIndex(free_start),
p->AddressToMarkbitIndex(free_end));
if (free_space_mode == ZAP_FREE_SPACE) {
ZapCode(free_start, size);
}
p->heap()->CreateFillerObjectAt(free_start, static_cast<int>(size),
ClearRecordedSlots::kNo);
}
Map map = object.synchronized_map();
int size = object.SizeFromMap(map);
free_start = free_end + size;
}
if (free_start != p->area_end()) {
CHECK_GT(p->area_end(), free_start);
size_t size = static_cast<size_t>(p->area_end() - free_start);
full_collector->non_atomic_marking_state()->bitmap(p)->ClearRange(
p->AddressToMarkbitIndex(free_start),
p->AddressToMarkbitIndex(p->area_end()));
if (free_space_mode == ZAP_FREE_SPACE) {
ZapCode(free_start, size);
}
p->heap()->CreateFillerObjectAt(free_start, static_cast<int>(size),
ClearRecordedSlots::kNo);
}
if (marking_mode == MarkingTreatmentMode::CLEAR) {
non_atomic_marking_state()->ClearLiveness(p);
p->ClearFlag(Page::SWEEP_TO_ITERATE);
}
}
namespace {
// Helper class for pruning the string table.
class YoungGenerationExternalStringTableCleaner : public RootVisitor {
public:
YoungGenerationExternalStringTableCleaner(
MinorMarkCompactCollector* collector)
: heap_(collector->heap()),
marking_state_(collector->non_atomic_marking_state()) {}
void VisitRootPointers(Root root, const char* description,
FullObjectSlot start, FullObjectSlot end) override {
DCHECK_EQ(static_cast<int>(root),
static_cast<int>(Root::kExternalStringsTable));
// Visit all HeapObject pointers in [start, end).
for (FullObjectSlot p = start; p < end; ++p) {
Object o = *p;
if (o.IsHeapObject()) {
HeapObject heap_object = HeapObject::cast(o);
if (marking_state_->IsWhite(heap_object)) {
if (o.IsExternalString()) {
heap_->FinalizeExternalString(String::cast(*p));
} else {
// The original external string may have been internalized.
DCHECK(o.IsThinString());
}
// Set the entry to the_hole_value (as deleted).
p.store(ReadOnlyRoots(heap_).the_hole_value());
}
}
}
}
private:
Heap* heap_;
MinorMarkCompactCollector::NonAtomicMarkingState* marking_state_;
};
// Marked young generation objects and all old generation objects will be
// retained.
class MinorMarkCompactWeakObjectRetainer : public WeakObjectRetainer {
public:
explicit MinorMarkCompactWeakObjectRetainer(
MinorMarkCompactCollector* collector)
: marking_state_(collector->non_atomic_marking_state()) {}
Object RetainAs(Object object) override {
HeapObject heap_object = HeapObject::cast(object);
if (!Heap::InYoungGeneration(heap_object)) return object;
// Young generation marking only marks to grey instead of black.
DCHECK(!marking_state_->IsBlack(heap_object));
if (marking_state_->IsGrey(heap_object)) {
return object;
}
return Object();
}
private:
MinorMarkCompactCollector::NonAtomicMarkingState* marking_state_;
};
} // namespace
void MinorMarkCompactCollector::ClearNonLiveReferences() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_CLEAR);
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_CLEAR_STRING_TABLE);
// Internalized strings are always stored in old space, so there is no need
// to clean them here.
YoungGenerationExternalStringTableCleaner external_visitor(this);
heap()->external_string_table_.IterateYoung(&external_visitor);
heap()->external_string_table_.CleanUpYoung();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_CLEAR_WEAK_LISTS);
// Process the weak references.
MinorMarkCompactWeakObjectRetainer retainer(this);
heap()->ProcessYoungWeakReferences(&retainer);
}
}
void MinorMarkCompactCollector::EvacuatePrologue() {
NewSpace* new_space = heap()->new_space();
// Append the list of new space pages to be processed.
for (Page* p :
PageRange(new_space->first_allocatable_address(), new_space->top())) {
new_space_evacuation_pages_.push_back(p);
}
new_space->Flip();
new_space->ResetLinearAllocationArea();
heap()->new_lo_space()->Flip();
heap()->new_lo_space()->ResetPendingObject();
}
void MinorMarkCompactCollector::EvacuateEpilogue() {
heap()->new_space()->set_age_mark(heap()->new_space()->top());
// Give pages that are queued to be freed back to the OS.
heap()->memory_allocator()->unmapper()->FreeQueuedChunks();
}
std::unique_ptr<UpdatingItem>
MinorMarkCompactCollector::CreateToSpaceUpdatingItem(MemoryChunk* chunk,
Address start,
Address end) {
return std::make_unique<ToSpaceUpdatingItem<NonAtomicMarkingState>>(
chunk, start, end, non_atomic_marking_state());
}
std::unique_ptr<UpdatingItem>
MinorMarkCompactCollector::CreateRememberedSetUpdatingItem(
MemoryChunk* chunk, RememberedSetUpdatingMode updating_mode) {
return std::make_unique<
RememberedSetUpdatingItem<NonAtomicMarkingState, MINOR_MARK_COMPACTOR>>(
heap(), non_atomic_marking_state(), chunk, updating_mode);
}
class PageMarkingItem;
class RootMarkingItem;
class YoungGenerationMarkingTask;
class YoungGenerationMarkingTask {
public:
YoungGenerationMarkingTask(
Isolate* isolate, MinorMarkCompactCollector* collector,
MinorMarkCompactCollector::MarkingWorklist* global_worklist, int task_id)
: marking_worklist_(global_worklist, task_id),
marking_state_(collector->marking_state()),
visitor_(marking_state_, global_worklist, task_id) {
local_live_bytes_.reserve(isolate->heap()->new_space()->Capacity() /
Page::kPageSize);
}
int slots() const { return slots_; }
void IncrementSlots() { ++slots_; }
void MarkObject(Object object) {
if (!Heap::InYoungGeneration(object)) return;
HeapObject heap_object = HeapObject::cast(object);
if (marking_state_->WhiteToGrey(heap_object)) {
const int size = visitor_.Visit(heap_object);
IncrementLiveBytes(heap_object, size);
}
}
void EmptyMarkingWorklist() {
HeapObject object;
while (marking_worklist_.Pop(&object)) {
const int size = visitor_.Visit(object);
IncrementLiveBytes(object, size);
}
}
void IncrementLiveBytes(HeapObject object, intptr_t bytes) {
local_live_bytes_[Page::FromHeapObject(object)] += bytes;
}
void FlushLiveBytes() {
for (auto pair : local_live_bytes_) {
marking_state_->IncrementLiveBytes(pair.first, pair.second);
}
}
private:
MinorMarkCompactCollector::MarkingWorklist::View marking_worklist_;
MinorMarkCompactCollector::MarkingState* marking_state_;
YoungGenerationMarkingVisitor visitor_;
std::unordered_map<Page*, intptr_t, Page::Hasher> local_live_bytes_;
int slots_ = 0;
};
class PageMarkingItem : public ParallelWorkItem {
public:
explicit PageMarkingItem(MemoryChunk* chunk) : chunk_(chunk) {}
~PageMarkingItem() = default;
void Process(YoungGenerationMarkingTask* task) {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"PageMarkingItem::Process");
base::MutexGuard guard(chunk_->mutex());
MarkUntypedPointers(task);
MarkTypedPointers(task);
}
private:
inline Heap* heap() { return chunk_->heap(); }
void MarkUntypedPointers(YoungGenerationMarkingTask* task) {
InvalidatedSlotsFilter filter = InvalidatedSlotsFilter::OldToNew(chunk_);
RememberedSet<OLD_TO_NEW>::Iterate(
chunk_,
[this, task, &filter](MaybeObjectSlot slot) {
if (!filter.IsValid(slot.address())) return REMOVE_SLOT;
return CheckAndMarkObject(task, slot);
},
SlotSet::FREE_EMPTY_BUCKETS);
filter = InvalidatedSlotsFilter::OldToNew(chunk_);
RememberedSetSweeping::Iterate(
chunk_,
[this, task, &filter](MaybeObjectSlot slot) {
if (!filter.IsValid(slot.address())) return REMOVE_SLOT;
return CheckAndMarkObject(task, slot);
},
SlotSet::FREE_EMPTY_BUCKETS);
}
void MarkTypedPointers(YoungGenerationMarkingTask* task) {
RememberedSet<OLD_TO_NEW>::IterateTyped(
chunk_, [=](SlotType slot_type, Address slot) {
return UpdateTypedSlotHelper::UpdateTypedSlot(
heap(), slot_type, slot, [this, task](FullMaybeObjectSlot slot) {
return CheckAndMarkObject(task, slot);
});
});
}
template <typename TSlot>
V8_INLINE SlotCallbackResult
CheckAndMarkObject(YoungGenerationMarkingTask* task, TSlot slot) {
static_assert(
std::is_same<TSlot, FullMaybeObjectSlot>::value ||
std::is_same<TSlot, MaybeObjectSlot>::value,
"Only FullMaybeObjectSlot and MaybeObjectSlot are expected here");
MaybeObject object = *slot;
if (Heap::InYoungGeneration(object)) {
// Marking happens before flipping the young generation, so the object
// has to be in a to page.
DCHECK(Heap::InToPage(object));
HeapObject heap_object;
bool success = object.GetHeapObject(&heap_object);
USE(success);
DCHECK(success);
task->MarkObject(heap_object);
task->IncrementSlots();
return KEEP_SLOT;
}
return REMOVE_SLOT;
}
MemoryChunk* chunk_;
};
class YoungGenerationMarkingJob : public v8::JobTask {
public:
YoungGenerationMarkingJob(
Isolate* isolate, MinorMarkCompactCollector* collector,
MinorMarkCompactCollector::MarkingWorklist* global_worklist,
std::vector<PageMarkingItem> marking_items, std::atomic<int>* slots)
: isolate_(isolate),
collector_(collector),
global_worklist_(global_worklist),
marking_items_(std::move(marking_items)),
remaining_marking_items_(marking_items_.size()),
generator_(marking_items_.size()),
slots_(slots) {}
void Run(JobDelegate* delegate) override {
if (delegate->IsJoiningThread()) {
TRACE_GC(collector_->heap()->tracer(),
GCTracer::Scope::MINOR_MC_MARK_PARALLEL);
ProcessItems(delegate);
} else {
TRACE_BACKGROUND_GC(
collector_->heap()->tracer(),
GCTracer::BackgroundScope::MINOR_MC_BACKGROUND_MARKING);
ProcessItems(delegate);
}
}
size_t GetMaxConcurrency(size_t worker_count) const override {
// Pages are not private to markers but we can still use them to estimate
// the amount of marking that is required.
const int kPagesPerTask = 2;
size_t items = remaining_marking_items_.load(std::memory_order_relaxed);
size_t num_tasks = std::max((items + 1) / kPagesPerTask,
global_worklist_->GlobalPoolSize());
return std::min<size_t>(
num_tasks, MinorMarkCompactCollector::MarkingWorklist::kMaxNumTasks);
}
private:
void ProcessItems(JobDelegate* delegate) {
double marking_time = 0.0;
{
TimedScope scope(&marking_time);
YoungGenerationMarkingTask task(isolate_, collector_, global_worklist_,
delegate->GetTaskId());
ProcessMarkingItems(&task);
task.EmptyMarkingWorklist();
task.FlushLiveBytes();
*slots_ += task.slots();
}
if (FLAG_trace_minor_mc_parallel_marking) {
PrintIsolate(collector_->isolate(), "marking[%p]: time=%f\n",
static_cast<void*>(this), marking_time);
}
}
void ProcessMarkingItems(YoungGenerationMarkingTask* task) {
while (remaining_marking_items_.load(std::memory_order_relaxed) > 0) {
base::Optional<size_t> index = generator_.GetNext();
if (!index) return;
for (size_t i = *index; i < marking_items_.size(); ++i) {
auto& work_item = marking_items_[i];
if (!work_item.TryAcquire()) break;
work_item.Process(task);
task->EmptyMarkingWorklist();
if (remaining_marking_items_.fetch_sub(1, std::memory_order_relaxed) <=
1) {
return;
}
}
}
}
Isolate* isolate_;
MinorMarkCompactCollector* collector_;
MinorMarkCompactCollector::MarkingWorklist* global_worklist_;
std::vector<PageMarkingItem> marking_items_;
std::atomic_size_t remaining_marking_items_{0};
IndexGenerator generator_;
std::atomic<int>* slots_;
};
void MinorMarkCompactCollector::MarkRootSetInParallel(
RootMarkingVisitor* root_visitor) {
std::atomic<int> slots;
{
std::vector<PageMarkingItem> marking_items;
// Seed the root set (roots + old->new set).
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_MARK_SEED);
isolate()->global_handles()->IdentifyWeakUnmodifiedObjects(
&JSObject::IsUnmodifiedApiObject);
// MinorMC treats all weak roots except for global handles as strong.
// That is why we don't set skip_weak = true here and instead visit
// global handles separately.
heap()->IterateRoots(
root_visitor, base::EnumSet<SkipRoot>{SkipRoot::kExternalStringTable,
SkipRoot::kGlobalHandles,
SkipRoot::kOldGeneration});
isolate()->global_handles()->IterateYoungStrongAndDependentRoots(
root_visitor);
// Create items for each page.
RememberedSet<OLD_TO_NEW>::IterateMemoryChunks(
heap(), [&marking_items](MemoryChunk* chunk) {
marking_items.emplace_back(chunk);
});
}
// Add tasks and run in parallel.
{
// The main thread might hold local items, while GlobalPoolSize() == 0.
// Flush to ensure these items are visible globally and picked up by the
// job.
worklist()->FlushToGlobal(kMainThreadTask);
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_MARK_ROOTS);
V8::GetCurrentPlatform()
->PostJob(v8::TaskPriority::kUserBlocking,
std::make_unique<YoungGenerationMarkingJob>(
isolate(), this, worklist(), std::move(marking_items),
&slots))
->Join();
DCHECK(worklist()->IsEmpty());
}
}
old_to_new_slots_ = slots;
}
void MinorMarkCompactCollector::MarkLiveObjects() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_MARK);
PostponeInterruptsScope postpone(isolate());
RootMarkingVisitor root_visitor(this);
MarkRootSetInParallel(&root_visitor);
// Mark rest on the main thread.
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_MARK_WEAK);
DrainMarkingWorklist();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_MARK_GLOBAL_HANDLES);
isolate()->global_handles()->MarkYoungWeakDeadObjectsPending(
&IsUnmarkedObjectForYoungGeneration);
isolate()->global_handles()->IterateYoungWeakDeadObjectsForFinalizers(
&root_visitor);
isolate()->global_handles()->IterateYoungWeakObjectsForPhantomHandles(
&root_visitor, &IsUnmarkedObjectForYoungGeneration);
DrainMarkingWorklist();
}
if (FLAG_minor_mc_trace_fragmentation) {
TraceFragmentation();
}
}
void MinorMarkCompactCollector::DrainMarkingWorklist() {
MarkingWorklist::View marking_worklist(worklist(), kMainMarker);
HeapObject object;
while (marking_worklist.Pop(&object)) {
DCHECK(!object.IsFreeSpaceOrFiller());
DCHECK(object.IsHeapObject());
DCHECK(heap()->Contains(object));
DCHECK(non_atomic_marking_state()->IsGrey(object));
main_marking_visitor()->Visit(object);
}
DCHECK(marking_worklist.IsLocalEmpty());
}
void MinorMarkCompactCollector::TraceFragmentation() {
NewSpace* new_space = heap()->new_space();
const std::array<size_t, 4> free_size_class_limits = {0, 1024, 2048, 4096};
size_t free_bytes_of_class[free_size_class_limits.size()] = {0};
size_t live_bytes = 0;
size_t allocatable_bytes = 0;
for (Page* p :
PageRange(new_space->first_allocatable_address(), new_space->top())) {
Address free_start = p->area_start();
for (auto object_and_size : LiveObjectRange<kGreyObjects>(
p, non_atomic_marking_state()->bitmap(p))) {
HeapObject const object = object_and_size.first;
Address free_end = object.address();
if (free_end != free_start) {
size_t free_bytes = free_end - free_start;
int free_bytes_index = 0;
for (auto free_size_class_limit : free_size_class_limits) {
if (free_bytes >= free_size_class_limit) {
free_bytes_of_class[free_bytes_index] += free_bytes;
}
free_bytes_index++;
}
}
Map map = object.synchronized_map();
int size = object.SizeFromMap(map);
live_bytes += size;
free_start = free_end + size;
}
size_t area_end =
p->Contains(new_space->top()) ? new_space->top() : p->area_end();
if (free_start != area_end) {
size_t free_bytes = area_end - free_start;
int free_bytes_index = 0;
for (auto free_size_class_limit : free_size_class_limits) {
if (free_bytes >= free_size_class_limit) {
free_bytes_of_class[free_bytes_index] += free_bytes;
}
free_bytes_index++;
}
}
allocatable_bytes += area_end - p->area_start();
CHECK_EQ(allocatable_bytes, live_bytes + free_bytes_of_class[0]);
}
PrintIsolate(
isolate(),
"Minor Mark-Compact Fragmentation: allocatable_bytes=%zu live_bytes=%zu "
"free_bytes=%zu free_bytes_1K=%zu free_bytes_2K=%zu free_bytes_4K=%zu\n",
allocatable_bytes, live_bytes, free_bytes_of_class[0],
free_bytes_of_class[1], free_bytes_of_class[2], free_bytes_of_class[3]);
}
void MinorMarkCompactCollector::Evacuate() {
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_EVACUATE);
base::MutexGuard guard(heap()->relocation_mutex());
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_EVACUATE_PROLOGUE);
EvacuatePrologue();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_EVACUATE_COPY);
EvacuatePagesInParallel();
}
UpdatePointersAfterEvacuation();
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_EVACUATE_REBALANCE);
if (!heap()->new_space()->Rebalance()) {
heap()->FatalProcessOutOfMemory("NewSpace::Rebalance");
}
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_EVACUATE_CLEAN_UP);
for (Page* p : new_space_evacuation_pages_) {
if (p->IsFlagSet(Page::PAGE_NEW_NEW_PROMOTION) ||
p->IsFlagSet(Page::PAGE_NEW_OLD_PROMOTION)) {
p->ClearFlag(Page::PAGE_NEW_NEW_PROMOTION);
p->ClearFlag(Page::PAGE_NEW_OLD_PROMOTION);
p->SetFlag(Page::SWEEP_TO_ITERATE);
sweep_to_iterate_pages_.push_back(p);
}
}
new_space_evacuation_pages_.clear();
}
{
TRACE_GC(heap()->tracer(), GCTracer::Scope::MINOR_MC_EVACUATE_EPILOGUE);
EvacuateEpilogue();
}
}
namespace {
class YoungGenerationEvacuator : public Evacuator {
public:
explicit YoungGenerationEvacuator(MinorMarkCompactCollector* collector)
: Evacuator(collector->heap(), &record_visitor_, &local_allocator_,
false),
record_visitor_(collector->heap()->mark_compact_collector()),
local_allocator_(heap_,
LocalSpaceKind::kCompactionSpaceForMinorMarkCompact),
collector_(collector) {}
GCTracer::BackgroundScope::ScopeId GetBackgroundTracingScope() override {
return GCTracer::BackgroundScope::MINOR_MC_BACKGROUND_EVACUATE_COPY;
}
GCTracer::Scope::ScopeId GetTracingScope() override {
return GCTracer::Scope::MINOR_MC_EVACUATE_COPY_PARALLEL;
}
protected:
void RawEvacuatePage(MemoryChunk* chunk, intptr_t* live_bytes) override;
YoungGenerationRecordMigratedSlotVisitor record_visitor_;
EvacuationAllocator local_allocator_;
MinorMarkCompactCollector* collector_;
};
void YoungGenerationEvacuator::RawEvacuatePage(MemoryChunk* chunk,
intptr_t* live_bytes) {
TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
"YoungGenerationEvacuator::RawEvacuatePage");
MinorMarkCompactCollector::NonAtomicMarkingState* marking_state =
collector_->non_atomic_marking_state();
*live_bytes = marking_state->live_bytes(chunk);
switch (ComputeEvacuationMode(chunk)) {
case kObjectsNewToOld:
LiveObjectVisitor::VisitGreyObjectsNoFail(
chunk, marking_state, &new_space_visitor_,
LiveObjectVisitor::kClearMarkbits);
break;
case kPageNewToOld:
LiveObjectVisitor::VisitGreyObjectsNoFail(
chunk, marking_state, &new_to_old_page_visitor_,
LiveObjectVisitor::kKeepMarking);
new_to_old_page_visitor_.account_moved_bytes(
marking_state->live_bytes(chunk));
if (!chunk->IsLargePage()) {
if (heap()->ShouldZapGarbage()) {
collector_->MakeIterable(static_cast<Page*>(chunk),
MarkingTreatmentMode::KEEP, ZAP_FREE_SPACE);
} else if (heap()->incremental_marking()->IsMarking()) {
// When incremental marking is on, we need to clear the mark bits of
// the full collector. We cannot yet discard the young generation mark
// bits as they are still relevant for pointers updating.
collector_->MakeIterable(static_cast<Page*>(chunk),
MarkingTreatmentMode::KEEP,
IGNORE_FREE_SPACE);
}
}
break;
case kPageNewToNew:
LiveObjectVisitor::VisitGreyObjectsNoFail(
chunk, marking_state, &new_to_new_page_visitor_,
LiveObjectVisitor::kKeepMarking);
new_to_new_page_visitor_.account_moved_bytes(
marking_state->live_bytes(chunk));
DCHECK(!chunk->IsLargePage());
if (heap()->ShouldZapGarbage()) {
collector_->MakeIterable(static_cast<Page*>(chunk),
MarkingTreatmentMode::KEEP, ZAP_FREE_SPACE);
} else if (heap()->incremental_marking()->IsMarking()) {
// When incremental marking is on, we need to clear the mark bits of
// the full collector. We cannot yet discard the young generation mark
// bits as they are still relevant for pointers updating.
collector_->MakeIterable(static_cast<Page*>(chunk),
MarkingTreatmentMode::KEEP, IGNORE_FREE_SPACE);
}
break;
case kObjectsOldToOld:
UNREACHABLE();
}
}
} // namespace
void MinorMarkCompactCollector::EvacuatePagesInParallel() {
std::vector<std::pair<ParallelWorkItem, MemoryChunk*>> evacuation_items;
intptr_t live_bytes = 0;
for (Page* page : new_space_evacuation_pages_) {
intptr_t live_bytes_on_page = non_atomic_marking_state()->live_bytes(page);
if (live_bytes_on_page == 0) continue;
live_bytes += live_bytes_on_page;
if (ShouldMovePage(page, live_bytes_on_page, false)) {
if (page->IsFlagSet(MemoryChunk::NEW_SPACE_BELOW_AGE_MARK)) {
EvacuateNewSpacePageVisitor<NEW_TO_OLD>::Move(page);
} else {
EvacuateNewSpacePageVisitor<NEW_TO_NEW>::Move(page);
}
}
evacuation_items.emplace_back(ParallelWorkItem{}, page);
}
// Promote young generation large objects.
for (auto it = heap()->new_lo_space()->begin();
it != heap()->new_lo_space()->end();) {
LargePage* current = *it;
it++;
HeapObject object = current->GetObject();
DCHECK(!non_atomic_marking_state_.IsBlack(object));
if (non_atomic_marking_state_.IsGrey(object)) {
heap_->lo_space()->PromoteNewLargeObject(current);
current->SetFlag(Page::PAGE_NEW_OLD_PROMOTION);
evacuation_items.emplace_back(ParallelWorkItem{}, current);
}
}
if (evacuation_items.empty()) return;
YoungGenerationMigrationObserver observer(heap(),
heap()->mark_compact_collector());
CreateAndExecuteEvacuationTasks<YoungGenerationEvacuator>(
this, std::move(evacuation_items), &observer, live_bytes);
}
#endif // ENABLE_MINOR_MC
} // namespace internal
} // namespace v8