namespace art HIDDEN { namespace gc { namespace collector {
static constexpr size_t kDefaultGcMarkStackSize = 2 * MB; // If kFilterModUnionCards then we attempt to filter cards that don't need to be dirty in the mod // union table. Disabled since it does not seem to help the pause much. static constexpr bool kFilterModUnionCards = kIsDebugBuild; // If kDisallowReadBarrierDuringScan is true then the GC aborts if there are any read barrier that // occur during ConcurrentCopying::Scan in GC thread. May be used to diagnose possibly unnecessary // read barriers. Only enabled for kIsDebugBuild to avoid performance hit. static constexpr bool kDisallowReadBarrierDuringScan = kIsDebugBuild; // Slow path mark stack size, increase this if the stack is getting full and it is causing // performance problems. static constexpr size_t kReadBarrierMarkStackSize = 512 * KB; // Verify that there are no missing card marks. static constexpr bool kVerifyNoMissingCardMarks = kIsDebugBuild;
ConcurrentCopying::ConcurrentCopying(Heap* heap, bool young_gen, bool use_generational_cc, const std::string& name_prefix, bool measure_read_barrier_slow_path)
: GarbageCollector(heap,
name_prefix + (name_prefix.empty() ? "" : " ") + "concurrent copying"),
region_space_(nullptr),
gc_barrier_(new Barrier(0)),
gc_mark_stack_(accounting::ObjectStack::Create("concurrent copying gc mark stack",
kDefaultGcMarkStackSize,
kDefaultGcMarkStackSize)),
use_generational_cc_(use_generational_cc),
young_gen_(young_gen),
rb_mark_bit_stack_(accounting::ObjectStack::Create("rb copying gc mark stack",
kReadBarrierMarkStackSize,
kReadBarrierMarkStackSize)),
rb_mark_bit_stack_full_(false),
mark_stack_lock_("concurrent copying mark stack lock", kMarkSweepMarkStackLock),
thread_running_gc_(nullptr),
is_marking_(false),
is_using_read_barrier_entrypoints_(false),
is_active_(false),
is_asserting_to_space_invariant_(false),
region_space_bitmap_(nullptr),
heap_mark_bitmap_(nullptr),
live_stack_freeze_size_(0),
from_space_num_bytes_at_first_pause_(0),
mark_stack_mode_(kMarkStackModeOff),
weak_ref_access_enabled_(true),
copied_live_bytes_ratio_sum_(0.f),
gc_count_(0),
reclaimed_bytes_ratio_sum_(0.f),
cumulative_bytes_moved_(0),
skipped_blocks_lock_("concurrent copying bytes blocks lock", kMarkSweepMarkStackLock),
measure_read_barrier_slow_path_(measure_read_barrier_slow_path),
mark_from_read_barrier_measurements_(false),
rb_slow_path_ns_(0),
rb_slow_path_count_(0),
rb_slow_path_count_gc_(0),
rb_slow_path_histogram_lock_("Read barrier histogram lock"),
rb_slow_path_time_histogram_("Mutator time in read barrier slow path", 500, 32),
rb_slow_path_count_total_(0),
rb_slow_path_count_gc_total_(0),
rb_table_(heap_->GetReadBarrierTable()),
force_evacuate_all_(false),
gc_grays_immune_objects_(false),
immune_gray_stack_lock_("concurrent copying immune gray stack lock",
kMarkSweepMarkStackLock),
num_bytes_allocated_before_gc_(0) {
static_assert(space::RegionSpace::kRegionSize == accounting::ReadBarrierTable::kRegionSize, "The region space size and the read barrier table region size must match");
CHECK(use_generational_cc_ || !young_gen_);
Thread* self = Thread::Current();
{
ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); // Cache this so that we won't have to lock heap_bitmap_lock_ in // Mark() which could cause a nested lock on heap_bitmap_lock_ // when GC causes a RB while doing GC or a lock order violation // (class_linker_lock_ and heap_bitmap_lock_).
heap_mark_bitmap_ = heap->GetMarkBitmap();
}
{
MutexLock mu(self, mark_stack_lock_); for (size_t i = 0; i < kMarkStackPoolSize; ++i) {
accounting::AtomicStack<mirror::Object>* mark_stack =
accounting::AtomicStack<mirror::Object>::Create( "thread local mark stack", GetMarkStackSize(), GetMarkStackSize());
pooled_mark_stacks_.push_back(mark_stack);
}
} // Return type of these functions are different. And even though the base class // is same, using ternary operator complains.
metrics::ArtMetrics* metrics = GetMetrics();
are_metrics_initialized_ = true; if (young_gen_) {
gc_time_histogram_ = metrics->YoungGcCollectionTime();
metrics_gc_count_ = metrics->YoungGcCount();
metrics_gc_count_delta_ = metrics->YoungGcCountDelta();
gc_throughput_histogram_ = metrics->YoungGcThroughput();
gc_tracing_throughput_hist_ = metrics->YoungGcTracingThroughput();
gc_throughput_avg_ = metrics->YoungGcThroughputAvg();
gc_tracing_throughput_avg_ = metrics->YoungGcTracingThroughputAvg();
gc_scanned_bytes_ = metrics->YoungGcScannedBytes();
gc_scanned_bytes_delta_ = metrics->YoungGcScannedBytesDelta();
gc_freed_bytes_ = metrics->YoungGcFreedBytes();
gc_freed_bytes_delta_ = metrics->YoungGcFreedBytesDelta();
gc_duration_ = metrics->YoungGcDuration();
gc_duration_delta_ = metrics->YoungGcDurationDelta();
gc_app_slow_path_during_gc_duration_delta_ = metrics->AppSlowPathDuringYoungGcDurationDelta();
} else {
gc_time_histogram_ = metrics->FullGcCollectionTime();
metrics_gc_count_ = metrics->FullGcCount();
metrics_gc_count_delta_ = metrics->FullGcCountDelta();
gc_throughput_histogram_ = metrics->FullGcThroughput();
gc_tracing_throughput_hist_ = metrics->FullGcTracingThroughput();
gc_throughput_avg_ = metrics->FullGcThroughputAvg();
gc_tracing_throughput_avg_ = metrics->FullGcTracingThroughputAvg();
gc_scanned_bytes_ = metrics->FullGcScannedBytes();
gc_scanned_bytes_delta_ = metrics->FullGcScannedBytesDelta();
gc_freed_bytes_ = metrics->FullGcFreedBytes();
gc_freed_bytes_delta_ = metrics->FullGcFreedBytesDelta();
gc_duration_ = metrics->FullGcDuration();
gc_duration_delta_ = metrics->FullGcDurationDelta();
gc_app_slow_path_during_gc_duration_delta_ = metrics->AppSlowPathDuringFullGcDurationDelta();
}
}
void ConcurrentCopying::MarkHeapReference(mirror::HeapReference<mirror::Object>* field, bool do_atomic_update) {
Thread* const self = Thread::Current(); if (UNLIKELY(do_atomic_update)) { // Used to mark the referent in DelayReferenceReferent in transaction mode.
mirror::Object* from_ref = field->AsMirrorPtr(); if (from_ref == nullptr) { return;
}
mirror::Object* to_ref = Mark(self, from_ref); if (from_ref != to_ref) { do { if (field->AsMirrorPtr() != from_ref) { // Concurrently overwritten by a mutator. break;
}
} while (!field->CasWeakRelaxed(from_ref, to_ref)); // "Relaxed" is not technically sufficient by C++ rules. However, we use a "release" // operation to originally store the forwarding pointer, or a constructor fence if we // directly obtained to_ref from Copy(). We then count on the fact that all later accesses // to the to_ref object are data/address-dependent on the forwarding pointer, and there is // no reasonable way for the compiler to eliminate that depenency. This is very similar to // the reasoning we must use for final fields in any case.
}
} else { // Used for preserving soft references, should be OK to not have a CAS here since there should be // no other threads which can trigger read barriers on the same referent during reference // processing.
field->Assign(Mark(self, field->AsMirrorPtr()));
}
}
void ConcurrentCopying::RunPhases() {
CHECK(kUseBakerReadBarrier || kUseTableLookupReadBarrier);
CHECK(!is_active_);
is_active_ = true;
Thread* self = Thread::Current();
thread_running_gc_ = self;
Locks::mutator_lock_->AssertNotHeld(self);
{
ReaderMutexLock mu(self, *Locks::mutator_lock_);
InitializePhase(); // In case of forced evacuation, all regions are evacuated and hence no // need to compute live_bytes. if (use_generational_cc_ && !young_gen_ && !force_evacuate_all_) {
MarkingPhase();
}
}
ScopedPriorityChange spc(self); if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) { // Switch to read barrier mark entrypoints before we gray the objects. This is required in case // a mutator sees a gray bit and dispatches on the entrypoint. (b/37876887).
ActivateReadBarrierEntrypoints(); // Gray dirty immune objects concurrently to reduce GC pause times. We re-process gray cards in // the pause.
ReaderMutexLock mu(self, *Locks::mutator_lock_);
GrayAllDirtyImmuneObjects();
spc.SetToNormalOrBetter();
}
FlipThreadRoots();
{
ReaderMutexLock mu(self, *Locks::mutator_lock_);
spc.Reset();
CopyingPhase();
} // Verify no from space refs. This causes a pause. if (kEnableNoFromSpaceRefsVerification) {
TimingLogger::ScopedTiming split("(Paused)VerifyNoFromSpaceReferences", GetTimings());
ScopedPause pause(this, false);
CheckEmptyMarkStack(); if (kVerboseMode) {
LOG(INFO) << "Verifying no from-space refs";
}
VerifyNoFromSpaceReferences(); if (kVerboseMode) {
LOG(INFO) << "Done verifying no from-space refs";
}
CheckEmptyMarkStack();
}
{
ReaderMutexLock mu(self, *Locks::mutator_lock_);
ReclaimPhase();
}
FinishPhase();
CHECK(is_active_);
is_active_ = false;
thread_running_gc_ = nullptr;
}
class ConcurrentCopying::ActivateReadBarrierEntrypointsCheckpoint : public Closure { public: explicit ActivateReadBarrierEntrypointsCheckpoint(ConcurrentCopying* concurrent_copying)
: concurrent_copying_(concurrent_copying) {}
void Run(Thread* thread) override NO_THREAD_SAFETY_ANALYSIS { // Note: self is not necessarily equal to thread since thread may be suspended.
Thread* self = Thread::Current();
DCHECK(thread == self ||
thread->IsSuspended() ||
thread->GetState() == ThreadState::kWaitingPerformingGc)
<< thread->GetState() << " thread " << thread << " self " << self; // Switch to the read barrier entrypoints.
thread->SetReadBarrierEntrypoints(); // If thread is a running mutator, then act on behalf of the garbage collector. // See the code in ThreadList::RunCheckpoint.
concurrent_copying_->GetBarrier().Pass(self);
}
class ConcurrentCopying::ActivateReadBarrierEntrypointsCallback : public Closure { public: explicit ActivateReadBarrierEntrypointsCallback(ConcurrentCopying* concurrent_copying)
: concurrent_copying_(concurrent_copying) {}
void Run([[maybe_unused]] Thread* self) override REQUIRES(Locks::thread_list_lock_) { // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint() // to avoid a race with ThreadList::Register().
CHECK(!concurrent_copying_->is_using_read_barrier_entrypoints_);
concurrent_copying_->is_using_read_barrier_entrypoints_ = true;
}
void ConcurrentCopying::ActivateReadBarrierEntrypoints() {
Thread* const self = Thread::Current();
ActivateReadBarrierEntrypointsCheckpoint checkpoint(this);
ThreadList* thread_list = Runtime::Current()->GetThreadList();
gc_barrier_->Init(self, 0);
ActivateReadBarrierEntrypointsCallback callback(this); const size_t barrier_count = thread_list->RunCheckpoint(&checkpoint, &callback); // If there are no threads to wait which implies that all the checkpoint functions are finished, // then no need to release the mutator lock. if (barrier_count == 0) { return;
}
ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
gc_barrier_->Increment(self, barrier_count);
}
void ConcurrentCopying::CreateInterRegionRefBitmaps() {
DCHECK(use_generational_cc_);
DCHECK(!region_space_inter_region_bitmap_.IsValid());
DCHECK(!non_moving_space_inter_region_bitmap_.IsValid());
DCHECK(region_space_ != nullptr);
DCHECK(heap_->non_moving_space_ != nullptr); // Region-space
region_space_inter_region_bitmap_ = accounting::ContinuousSpaceBitmap::Create( "region-space inter region ref bitmap", reinterpret_cast<uint8_t*>(region_space_->Begin()),
region_space_->Limit() - region_space_->Begin());
CHECK(region_space_inter_region_bitmap_.IsValid())
<< "Couldn't allocate region-space inter region ref bitmap";
// non-moving-space
non_moving_space_inter_region_bitmap_ = accounting::ContinuousSpaceBitmap::Create( "non-moving-space inter region ref bitmap", reinterpret_cast<uint8_t*>(heap_->non_moving_space_->Begin()),
heap_->non_moving_space_->Limit() - heap_->non_moving_space_->Begin());
CHECK(non_moving_space_inter_region_bitmap_.IsValid())
<< "Couldn't allocate non-moving-space inter region ref bitmap";
}
void ConcurrentCopying::BindBitmaps() {
Thread* self = Thread::Current();
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); // Mark all of the spaces we never collect as immune. for (constauto& space : heap_->GetContinuousSpaces()) { if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect ||
space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) {
CHECK(space->IsZygoteSpace() || space->IsImageSpace());
immune_spaces_.AddSpace(space);
} else {
CHECK(!space->IsZygoteSpace());
CHECK(!space->IsImageSpace());
CHECK(space == region_space_ || space == heap_->non_moving_space_); if (use_generational_cc_) { if (space == region_space_) {
region_space_bitmap_ = region_space_->GetMarkBitmap();
} elseif (young_gen_ && space->IsContinuousMemMapAllocSpace()) {
DCHECK_EQ(space->GetGcRetentionPolicy(), space::kGcRetentionPolicyAlwaysCollect);
space->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap();
} if (young_gen_) { // Age all of the cards for the region space so that we know which evac regions to scan.
heap_->GetCardTable()->ModifyCardsAtomic(space->Begin(),
space->End(),
AgeCardVisitor(),
VoidFunctor());
} else { // In a full-heap GC cycle, the card-table corresponding to region-space and // non-moving space can be cleared, because this cycle only needs to // capture writes during the marking phase of this cycle to catch // objects that skipped marking due to heap mutation. Furthermore, // if the next GC is a young-gen cycle, then it only needs writes to // be captured after the thread-flip of this GC cycle, as that is when // the young-gen for the next GC cycle starts getting populated.
heap_->GetCardTable()->ClearCardRange(space->Begin(), space->Limit());
}
} else { if (space == region_space_) { // It is OK to clear the bitmap with mutators running since the only place it is read is // VisitObjects which has exclusion with CC.
region_space_bitmap_ = region_space_->GetMarkBitmap();
region_space_bitmap_->Clear(ShouldEagerlyReleaseMemoryToOS());
}
}
}
} if (use_generational_cc_ && young_gen_) { for (constauto& space : GetHeap()->GetDiscontinuousSpaces()) {
CHECK(space->IsLargeObjectSpace());
space->AsLargeObjectSpace()->CopyLiveToMarked();
}
}
}
force_evacuate_all_ = false; if (!use_generational_cc_ || !young_gen_) { if (gc_cause == kGcCauseExplicit ||
gc_cause == kGcCauseCollectorTransition ||
GetCurrentIteration()->GetClearSoftReferences()) {
force_evacuate_all_ = true;
}
} if (kUseBakerReadBarrier) {
updated_all_immune_objects_.store(false, std::memory_order_relaxed); // GC may gray immune objects in the thread flip.
gc_grays_immune_objects_ = true; if (kIsDebugBuild) {
MutexLock mu(Thread::Current(), immune_gray_stack_lock_);
DCHECK(immune_gray_stack_.empty());
}
} if (use_generational_cc_) {
done_scanning_.store(false, std::memory_order_release);
}
BindBitmaps(); if (kVerboseMode) {
LOG(INFO) << "young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha;
LOG(INFO) << "force_evacuate_all=" << std::boolalpha << force_evacuate_all_ << std::noboolalpha;
LOG(INFO) << "Largest immune region: " << immune_spaces_.GetLargestImmuneRegion().Begin()
<< "-" << immune_spaces_.GetLargestImmuneRegion().End(); for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
LOG(INFO) << "Immune space: " << *space;
}
LOG(INFO) << "GC end of InitializePhase";
} if (use_generational_cc_ && !young_gen_) {
region_space_bitmap_->Clear(ShouldEagerlyReleaseMemoryToOS());
}
mark_stack_mode_.store(ConcurrentCopying::kMarkStackModeThreadLocal, std::memory_order_release); // Mark all of the zygote large objects without graying them.
MarkZygoteLargeObjects();
}
// Used to switch the thread roots of a thread from from-space refs to to-space refs. class ConcurrentCopying::ThreadFlipVisitor : public Closure, public RootVisitor { public:
ThreadFlipVisitor(ConcurrentCopying* concurrent_copying, bool use_tlab)
: concurrent_copying_(concurrent_copying), use_tlab_(use_tlab) {
}
void Run(Thread* thread) override REQUIRES_SHARED(Locks::mutator_lock_) { // We are either running this in the target thread, or the target thread will wait for us // before switching back to runnable.
Thread* self = Thread::Current();
CHECK(thread == self || thread->GetState() != ThreadState::kRunnable)
<< thread->GetState() << " thread " << thread << " self " << self;
thread->SetIsGcMarkingAndUpdateEntrypoints(true); if (use_tlab_ && thread->HasTlab()) {
concurrent_copying_->region_space_->RevokeThreadLocalBuffers(thread, /*reuse=*/ false);
} if (kUseThreadLocalAllocationStack) {
thread->RevokeThreadLocalAllocationStack();
}
ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); // We can use the non-CAS VisitRoots functions below because we update thread-local GC roots // only.
thread->VisitRoots(this, kVisitRootFlagAllRoots);
}
// Called back from Runtime::FlipThreadRoots() during a pause. class ConcurrentCopying::FlipCallback : public Closure { public: explicit FlipCallback(ConcurrentCopying* concurrent_copying)
: concurrent_copying_(concurrent_copying) {
}
void Run(Thread* thread) override REQUIRES(Locks::mutator_lock_) {
ConcurrentCopying* cc = concurrent_copying_;
TimingLogger::ScopedTiming split("(Paused)FlipCallback", cc->GetTimings()); // Note: self is not necessarily equal to thread since thread may be suspended.
Thread* self = Thread::Current(); if (kVerifyNoMissingCardMarks && cc->young_gen_) {
cc->VerifyNoMissingCardMarks();
}
CHECK_EQ(thread, self);
Locks::mutator_lock_->AssertExclusiveHeld(self);
space::RegionSpace::EvacMode evac_mode = space::RegionSpace::kEvacModeLivePercentNewlyAllocated; if (cc->young_gen_) {
CHECK(!cc->force_evacuate_all_);
evac_mode = space::RegionSpace::kEvacModeNewlyAllocated;
} elseif (cc->force_evacuate_all_) {
evac_mode = space::RegionSpace::kEvacModeForceAll;
}
{
TimingLogger::ScopedTiming split2("(Paused)SetFromSpace", cc->GetTimings()); // Only change live bytes for 1-phase full heap CC, that is if we are either not running in // generational-mode, or it's an 'evacuate-all' mode GC.
cc->region_space_->SetFromSpace(
cc->rb_table_,
evac_mode, /*clear_live_bytes=*/ !cc->use_generational_cc_ || cc->force_evacuate_all_);
}
cc->SwapStacks(); if (ConcurrentCopying::kEnableFromSpaceAccountingCheck) {
cc->RecordLiveStackFreezeSize(self);
cc->from_space_num_bytes_at_first_pause_ = cc->region_space_->GetBytesAllocated();
}
cc->is_marking_ = true;
cc->app_slow_path_start_time_ = MilliTime(); if (kIsDebugBuild && !cc->use_generational_cc_) {
cc->region_space_->AssertAllRegionLiveBytesZeroOrCleared();
}
Runtime* runtime = Runtime::Current(); if (UNLIKELY(runtime->IsActiveTransaction())) {
CHECK(runtime->IsAotCompiler());
TimingLogger::ScopedTiming split3("(Paused)VisitTransactionRoots", cc->GetTimings());
runtime->GetClassLinker()->VisitTransactionRoots(cc);
} if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) {
cc->GrayAllNewlyDirtyImmuneObjects(); if (kIsDebugBuild) { // Check that all non-gray immune objects only reference immune objects.
cc->VerifyGrayImmuneObjects();
}
}
ObjPtr<mirror::Class> java_lang_Object =
GetClassRoot<mirror::Object, kWithoutReadBarrier>(runtime->GetClassLinker());
DCHECK(java_lang_Object != nullptr);
cc->java_lang_Object_ = down_cast<mirror::Class*>(cc->Mark(thread, java_lang_Object.Ptr()));
}
void CheckReference(ObjPtr<mirror::Object> ref,
ObjPtr<mirror::Object> holder,
MemberOffset offset) const
REQUIRES_SHARED(Locks::mutator_lock_) { if (ref != nullptr) { if (!collector_->immune_spaces_.ContainsObject(ref.Ptr())) { // Not immune, must be a zygote large object. auto* heap = Runtime::Current()->GetHeap();
CHECK(heap->IsZygoteLargeObject(ref.Ptr()))
<< "Non gray object references non immune, non zygote large object " << ref << " "
<< mirror::Object::PrettyTypeOf(ref) << " in holder " << holder << " "
<< mirror::Object::PrettyTypeOf(holder) << " offset=" << offset.Uint32Value();
} else { // Make sure the large object class is immune since we will never scan the large object.
CHECK(collector_->immune_spaces_.ContainsObject(
ref->GetClass<kVerifyNone, kWithoutReadBarrier>()));
}
}
}
};
void ConcurrentCopying::VerifyGrayImmuneObjects() {
TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings()); for (auto& space : immune_spaces_.GetSpaces()) {
DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
VerifyGrayImmuneObjectsVisitor visitor(this);
live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()), reinterpret_cast<uintptr_t>(space->Limit()),
[&visitor](mirror::Object* obj)
REQUIRES_SHARED(Locks::mutator_lock_) { // If an object is not gray, it should only have references to things in the immune spaces. if (obj->GetReadBarrierState() != ReadBarrier::GrayState()) {
obj->VisitReferences</*kVisitNativeRoots=*/true,
kDefaultVerifyFlags,
kWithoutReadBarrier>(visitor, visitor);
}
});
}
}
ALWAYS_INLINE voidoperator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) { if (kUseBakerReadBarrier && obj->GetReadBarrierState() == ReadBarrier::NonGrayState()) { if (kConcurrent) {
Locks::mutator_lock_->AssertSharedHeld(self_);
obj->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(), ReadBarrier::GrayState()); // Mod union table VisitObjects may visit the same object multiple times so we can't check // the result of the atomic set.
} else {
Locks::mutator_lock_->AssertExclusiveHeld(self_);
obj->SetReadBarrierState(ReadBarrier::GrayState());
}
}
}
void ConcurrentCopying::GrayAllDirtyImmuneObjects() {
TimingLogger::ScopedTiming split("GrayAllDirtyImmuneObjects", GetTimings());
accounting::CardTable* const card_table = heap_->GetCardTable();
Thread* const self = Thread::Current(); using VisitorType = GrayImmuneObjectVisitor</* kIsConcurrent= */ true>;
VisitorType visitor(self);
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); // Mark all the objects on dirty cards since these may point to objects in other space. // Once these are marked, the GC will eventually clear them later. // Table is non null for boot image and zygote spaces. It is only null for application image // spaces. if (table != nullptr) {
table->ProcessCards();
table->VisitObjects(&VisitorType::Callback, &visitor); // Don't clear cards here since we need to rescan in the pause. If we cleared the cards here, // there would be races with the mutator marking new cards.
} else { // Keep cards aged if we don't have a mod-union table since we may need to scan them in future // GCs. This case is for app images.
card_table->ModifyCardsAtomic(
space->Begin(),
space->End(),
[](uint8_t card) { return (card != gc::accounting::CardTable::kCardClean)
? gc::accounting::CardTable::kCardAged
: card;
}, /* card modified visitor */ VoidFunctor());
card_table->Scan</*kClearCard=*/ false>(space->GetMarkBitmap(),
space->Begin(),
space->End(),
visitor,
gc::accounting::CardTable::kCardAged);
}
}
}
// Don't need to scan aged cards since we did these before the pause. Note that scanning cards // also handles the mod-union table cards.
card_table->Scan</*kClearCard=*/ false>(space->GetMarkBitmap(),
space->Begin(),
space->End(),
visitor,
gc::accounting::CardTable::kCardDirty); if (table != nullptr) { // Add the cards to the mod-union table so that we can clear cards to save RAM.
table->ProcessCards();
TimingLogger::ScopedTiming split2("(Paused)ClearCards", GetTimings());
card_table->ClearCardRange(space->Begin(),
AlignDown(space->End(), accounting::CardTable::kCardSize));
}
} // Since all of the objects that may point to other spaces are gray, we can avoid all the read // barriers in the immune spaces.
updated_all_immune_objects_.store(true, std::memory_order_relaxed);
}
// Used to visit objects in the immune spaces. inlinevoid ConcurrentCopying::ScanImmuneObject(mirror::Object* obj) {
DCHECK(obj != nullptr);
DCHECK(immune_spaces_.ContainsObject(obj)); // Update the fields without graying it or pushing it onto the mark stack. if (use_generational_cc_ && young_gen_) { // Young GC does not care about references to unevac space. It is safe to not gray these as // long as scan immune objects happens after scanning the dirty cards.
Scan<true>(obj);
} else {
Scan<false>(obj);
}
}
class ConcurrentCopying::ImmuneSpaceScanObjVisitor { public: explicit ImmuneSpaceScanObjVisitor(ConcurrentCopying* cc)
: collector_(cc) {}
ALWAYS_INLINE voidoperator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) { if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) { // Only need to scan gray objects. if (obj->GetReadBarrierState() == ReadBarrier::GrayState()) {
collector_->ScanImmuneObject(obj); // Done scanning the object, go back to black (non-gray). Release order // required to ensure that stores of to-space references done by // ScanImmuneObject() are visible before state change. bool success = obj->AtomicSetReadBarrierState(
ReadBarrier::GrayState(), ReadBarrier::NonGrayState(), std::memory_order_release);
CHECK(success)
<< Runtime::Current()->GetHeap()->GetVerification()->DumpObjectInfo(obj, "failed CAS");
}
} else {
collector_->ScanImmuneObject(obj);
}
}
class ConcurrentCopying::CaptureThreadRootsForMarkingAndCheckpoint : public RevokeThreadLocalMarkStackCheckpoint { public: explicit CaptureThreadRootsForMarkingAndCheckpoint(ConcurrentCopying* cc) :
RevokeThreadLocalMarkStackCheckpoint(cc, /* disable_weak_ref_access */ false) {}
void Run(Thread* thread) override
REQUIRES_SHARED(Locks::mutator_lock_) {
Thread* const self = Thread::Current();
ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); // We can use the non-CAS VisitRoots functions below because we update thread-local GC roots // only.
CaptureRootsForMarkingVisitor</*kAtomicTestAndSet*/ true> visitor(concurrent_copying_, self);
thread->VisitRoots(&visitor, kVisitRootFlagAllRoots); // If thread_running_gc_ performed the root visit then its thread-local // mark-stack should be null as we directly push to gc_mark_stack_.
CHECK(self == thread || self->GetThreadLocalMarkStack() == nullptr); // Barrier handling is done in the base class' Run() below.
RevokeThreadLocalMarkStackCheckpoint::Run(thread);
}
};
void ConcurrentCopying::CaptureThreadRootsForMarking() {
TimingLogger::ScopedTiming split("CaptureThreadRootsForMarking", GetTimings()); if (kVerboseMode) {
LOG(INFO) << "time=" << region_space_->Time();
region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
}
Thread* const self = Thread::Current();
CaptureThreadRootsForMarkingAndCheckpoint check_point(this);
ThreadList* thread_list = Runtime::Current()->GetThreadList();
gc_barrier_->Init(self, 0);
size_t barrier_count = thread_list->RunCheckpoint(&check_point, /* callback */ nullptr); // If there are no threads to wait which implys that all the checkpoint functions are finished, // then no need to release the mutator lock. if (barrier_count == 0) { return;
}
Locks::mutator_lock_->SharedUnlock(self);
{
ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
gc_barrier_->Increment(self, barrier_count);
}
Locks::mutator_lock_->SharedLock(self); if (kVerboseMode) {
LOG(INFO) << "time=" << region_space_->Time();
region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
LOG(INFO) << "GC end of CaptureThreadRootsForMarking";
}
}
// Used to scan ref fields of an object. template <bool kHandleInterRegionRefs> class ConcurrentCopying::ComputeLiveBytesAndMarkRefFieldsVisitor { public: explicit ComputeLiveBytesAndMarkRefFieldsVisitor(ConcurrentCopying* collector,
size_t obj_region_idx)
: collector_(collector),
obj_region_idx_(obj_region_idx),
contains_inter_region_idx_(false) {}
voidoperator()(mirror::Object* obj, MemberOffset offset, bool/* is_static */) const
ALWAYS_INLINE
REQUIRES_SHARED(Locks::mutator_lock_)
REQUIRES_SHARED(Locks::heap_bitmap_lock_) {
DCHECK_EQ(collector_->RegionSpace()->RegionIdxForRef(obj), obj_region_idx_);
DCHECK(kHandleInterRegionRefs || collector_->immune_spaces_.ContainsObject(obj));
mirror::Object* ref =
obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset); // TODO(lokeshgidra): Remove the following condition once b/173676071 is fixed. if (UNLIKELY(ref == nullptr && offset == mirror::Object::ClassOffset())) { // It has been verified as a race condition (see b/173676071)! After a small // wait when we reload the class pointer, it turns out to be a valid class // object. So as a workaround, we can continue execution and log an error // that this happened. for (size_t i = 0; i < 1000; i++) { // Wait for 1ms at a time. Don't wait for more than 1 second in total.
usleep(1000);
ref = obj->GetClass<kVerifyNone, kWithoutReadBarrier>(); if (ref != nullptr) {
LOG(ERROR) << "klass pointer for obj: "
<< obj << " (" << mirror::Object::PrettyTypeOf(obj)
<< ") found to be null first. Reloading after a small wait fetched klass: "
<< ref << " (" << mirror::Object::PrettyTypeOf(ref) << ")"; break;
}
}
if (UNLIKELY(ref == nullptr)) { // It must be heap corruption. Remove memory protection and dump data.
collector_->region_space_->Unprotect();
LOG(FATAL_WITHOUT_ABORT) << "klass pointer for ref: " << obj << " found to be null.";
collector_->heap_->GetVerification()->LogHeapCorruption(obj, offset, ref, /* fatal */ true);
}
}
CheckReference(ref);
}
voidoperator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const
REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
DCHECK(klass->IsTypeOfReferenceClass()); // If the referent is not null, then we must re-visit the object during // copying phase to enqueue it for delayed processing and setting // read-barrier state to gray to ensure that call to GetReferent() triggers // the read-barrier. We use same data structure that is used to remember // objects with inter-region refs for this purpose too. if (kHandleInterRegionRefs
&& !contains_inter_region_idx_
&& ref->AsReference()->GetReferent<kWithoutReadBarrier>() != nullptr) {
contains_inter_region_idx_ = true;
}
}
private: void CheckReference(mirror::Object* ref) const
REQUIRES_SHARED(Locks::mutator_lock_) { if (ref == nullptr) { // Nothing to do. return;
} if (!collector_->TestAndSetMarkBitForRef(ref)) {
collector_->PushOntoLocalMarkStack(ref);
} if (kHandleInterRegionRefs && !contains_inter_region_idx_) {
size_t ref_region_idx = collector_->RegionSpace()->RegionIdxForRef(ref); // If a region-space object refers to an outside object, we will have a // mismatch of region idx, but the object need not be re-visited in // copying phase. if (ref_region_idx != static_cast<size_t>(-1) && obj_region_idx_ != ref_region_idx) {
contains_inter_region_idx_ = true;
}
}
}
void ConcurrentCopying::AddLiveBytesAndScanRef(mirror::Object* ref) {
DCHECK(ref != nullptr);
DCHECK(!immune_spaces_.ContainsObject(ref));
DCHECK(TestMarkBitmapForRef(ref));
size_t obj_region_idx = static_cast<size_t>(-1); if (LIKELY(region_space_->HasAddress(ref))) {
obj_region_idx = region_space_->RegionIdxForRefUnchecked(ref); // Add live bytes to the corresponding region if (!region_space_->IsRegionNewlyAllocated(obj_region_idx)) { // Newly Allocated regions are always chosen for evacuation. So no need // to update live_bytes_.
size_t obj_size = ref->SizeOf<kDefaultVerifyFlags>();
size_t alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment);
region_space_->AddLiveBytes(ref, alloc_size);
}
}
ComputeLiveBytesAndMarkRefFieldsVisitor</*kHandleInterRegionRefs*/ true>
visitor(this, obj_region_idx);
ref->VisitReferences</*kVisitNativeRoots=*/ true, kDefaultVerifyFlags, kWithoutReadBarrier>(
visitor, visitor); // Mark the corresponding card dirty if the object contains any // inter-region reference. if (visitor.ContainsInterRegionRefs()) { if (obj_region_idx == static_cast<size_t>(-1)) { // If an inter-region ref has been found in a non-region-space, then it // must be non-moving-space. This is because this function cannot be // called on a immune-space object, and a large-object-space object has // only class object reference, which is either in some immune-space, or // in non-moving-space.
DCHECK(heap_->non_moving_space_->HasAddress(ref));
non_moving_space_inter_region_bitmap_.Set(ref);
} else {
region_space_inter_region_bitmap_.Set(ref);
}
}
}
template <bool kAtomic> bool ConcurrentCopying::TestAndSetMarkBitForRef(mirror::Object* ref) {
accounting::ContinuousSpaceBitmap* bitmap = nullptr;
accounting::LargeObjectBitmap* los_bitmap = nullptr; if (LIKELY(region_space_->HasAddress(ref))) {
bitmap = region_space_bitmap_;
} elseif (heap_->GetNonMovingSpace()->HasAddress(ref)) {
bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
} elseif (immune_spaces_.ContainsObject(ref)) { // References to immune space objects are always live.
DCHECK(heap_mark_bitmap_->GetContinuousSpaceBitmap(ref)->Test(ref)); returntrue;
} else { // Should be a large object. Must be aligned and the LOS must exist. if (kIsDebugBuild && (!IsAlignedParam(ref, space::LargeObjectSpace::ObjectAlignment()) ||
heap_->GetLargeObjectsSpace() == nullptr)) { // It must be heap corruption. Remove memory protection and dump data.
region_space_->Unprotect();
heap_->GetVerification()->LogHeapCorruption(/* obj */ nullptr,
MemberOffset(0),
ref, /* fatal */ true);
}
los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
} if (kAtomic) { return (bitmap != nullptr) ? bitmap->AtomicTestAndSet(ref) : los_bitmap->AtomicTestAndSet(ref);
} else { return (bitmap != nullptr) ? bitmap->Set(ref) : los_bitmap->Set(ref);
}
}
bool ConcurrentCopying::TestMarkBitmapForRef(mirror::Object* ref) { if (LIKELY(region_space_->HasAddress(ref))) { return region_space_bitmap_->Test(ref);
} elseif (heap_->GetNonMovingSpace()->HasAddress(ref)) { return heap_->GetNonMovingSpace()->GetMarkBitmap()->Test(ref);
} elseif (immune_spaces_.ContainsObject(ref)) { // References to immune space objects are always live.
DCHECK(heap_mark_bitmap_->GetContinuousSpaceBitmap(ref)->Test(ref)); returntrue;
} else { // Should be a large object. Must be aligned and the LOS must exist. if (kIsDebugBuild && (!IsAlignedParam(ref, space::LargeObjectSpace::ObjectAlignment()) ||
heap_->GetLargeObjectsSpace() == nullptr)) { // It must be heap corruption. Remove memory protection and dump data.
region_space_->Unprotect();
heap_->GetVerification()->LogHeapCorruption(/* obj */ nullptr,
MemberOffset(0),
ref, /* fatal */ true);
} return heap_->GetLargeObjectsSpace()->GetMarkBitmap()->Test(ref);
}
}
void ConcurrentCopying::MarkingPhase() {
TimingLogger::ScopedTiming split("MarkingPhase", GetTimings()); if (kVerboseMode) {
LOG(INFO) << "GC MarkingPhase";
}
accounting::CardTable* const card_table = heap_->GetCardTable();
Thread* const self = Thread::Current();
CHECK_EQ(self, thread_running_gc_); // Clear live_bytes_ of every non-free region, except the ones that are newly // allocated.
region_space_->SetAllRegionLiveBytesZero(); if (kIsDebugBuild) {
region_space_->AssertAllRegionLiveBytesZeroOrCleared();
} // Scan immune spaces
{
TimingLogger::ScopedTiming split2("ScanImmuneSpaces", GetTimings()); for (auto& space : immune_spaces_.GetSpaces()) {
DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
ImmuneSpaceCaptureRefsVisitor visitor(this); if (table != nullptr) {
table->VisitObjects(ImmuneSpaceCaptureRefsVisitor::Callback, &visitor);
} else {
WriterMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
card_table->Scan<false>(
live_bitmap,
space->Begin(),
space->Limit(),
visitor,
accounting::CardTable::kCardDirty - 1);
}
}
} // Scan runtime roots
{
TimingLogger::ScopedTiming split2("VisitConcurrentRoots", GetTimings());
CaptureRootsForMarkingVisitor visitor(this, self);
Runtime::Current()->VisitConcurrentRoots(&visitor, kVisitRootFlagAllRoots);
}
{ // TODO: don't visit the transaction roots if it's not active.
TimingLogger::ScopedTiming split2("VisitNonThreadRoots", GetTimings());
CaptureRootsForMarkingVisitor visitor(this, self);
Runtime::Current()->VisitNonThreadRoots(&visitor);
} // Capture thread roots
CaptureThreadRootsForMarking(); // Process mark stack
ProcessMarkStackForMarkingAndComputeLiveBytes();
if (kVerboseMode) {
LOG(INFO) << "GC end of MarkingPhase";
}
}
template <bool kNoUnEvac> void ConcurrentCopying::ScanDirtyObject(mirror::Object* obj) {
Scan<kNoUnEvac>(obj); // Set the read-barrier state of a reference-type object to gray if its // referent is not marked yet. This is to ensure that if GetReferent() is // called, it triggers the read-barrier to process the referent before use. if (UNLIKELY((obj->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass()))) {
mirror::Object* referent =
obj->AsReference<kVerifyNone, kWithoutReadBarrier>()->GetReferent<kWithoutReadBarrier>(); if (referent != nullptr && !IsInToSpace(referent)) {
obj->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(), ReadBarrier::GrayState());
}
}
}
// Concurrently mark roots that are guarded by read barriers and process the mark stack. void ConcurrentCopying::CopyingPhase() {
TimingLogger::ScopedTiming split("CopyingPhase", GetTimings()); if (kVerboseMode) {
LOG(INFO) << "GC CopyingPhase";
}
Thread* self = Thread::Current();
accounting::CardTable* const card_table = heap_->GetCardTable(); if (kIsDebugBuild) {
MutexLock mu(self, *Locks::thread_list_lock_);
CHECK(weak_ref_access_enabled_);
}
// Scan immune spaces. // Update all the fields in the immune spaces first without graying the objects so that we // minimize dirty pages in the immune spaces. Note mutators can concurrently access and gray some // of the objects. if (kUseBakerReadBarrier) {
gc_grays_immune_objects_ = false;
} if (use_generational_cc_) { if (kVerboseMode) {
LOG(INFO) << "GC ScanCardsForSpace";
}
TimingLogger::ScopedTiming split2("ScanCardsForSpace", GetTimings());
WriterMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
CHECK(!done_scanning_.load(std::memory_order_relaxed)); if (kIsDebugBuild) { // Leave some time for mutators to race ahead to try and find races between the GC card // scanning and mutators reading references.
usleep(10 * 1000);
} for (space::ContinuousSpace* space : GetHeap()->GetContinuousSpaces()) { if (space->IsImageSpace() || space->IsZygoteSpace()) { // Image and zygote spaces are already handled since we gray the objects in the pause. continue;
} // Scan all of the objects on dirty cards in unevac from space, and non moving space. These // are from previous GCs (or from marking phase of 2-phase full GC) and may reference things // in the from space. // // Note that we do not need to process the large-object space (the only discontinuous space) // as it contains only large string objects and large primitive array objects, that have no // reference to other objects, except their class. There is no need to scan these large // objects, as the String class and the primitive array classes are expected to never move // during a collection: // - In the case where we run with a boot image, these classes are part of the image space, // which is an immune space. // - In the case where we run without a boot image, these classes are allocated in the // non-moving space (see art::ClassLinker::InitWithoutImage).
card_table->Scan<false>(
space->GetMarkBitmap(),
space->Begin(),
space->End(),
[this, space](mirror::Object* obj)
REQUIRES(Locks::heap_bitmap_lock_)
REQUIRES_SHARED(Locks::mutator_lock_) { // TODO: This code may be refactored to avoid scanning object while // done_scanning_ is false by setting rb_state to gray, and pushing the // object on mark stack. However, it will also require clearing the // corresponding mark-bit and, for region space objects, // decrementing the object's size from the corresponding region's // live_bytes. if (young_gen_) { // Don't push or gray unevac refs. if (kIsDebugBuild && space == region_space_) { // We may get unevac large objects. if (!region_space_->IsInUnevacFromSpace(obj)) {
CHECK(region_space_bitmap_->Test(obj));
region_space_->DumpRegionForObject(LOG_STREAM(FATAL_WITHOUT_ABORT), obj);
LOG(FATAL) << "Scanning " << obj << " not in unevac space";
}
}
ScanDirtyObject</*kNoUnEvac*/ true>(obj);
} elseif (space != region_space_) {
DCHECK(space == heap_->non_moving_space_); // We need to process un-evac references as they may be unprocessed, // if they skipped the marking phase due to heap mutation.
ScanDirtyObject</*kNoUnEvac*/ false>(obj);
non_moving_space_inter_region_bitmap_.Clear(obj);
} elseif (region_space_->IsInUnevacFromSpace(obj)) {
ScanDirtyObject</*kNoUnEvac*/ false>(obj);
region_space_inter_region_bitmap_.Clear(obj);
}
},
accounting::CardTable::kCardAged);
if (!young_gen_) { auto visitor = [this](mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_) { // We don't need to process un-evac references as any unprocessed // ones will be taken care of in the card-table scan above.
ScanDirtyObject</*kNoUnEvac*/ true>(obj);
}; if (space == region_space_) {
region_space_->ScanUnevacFromSpace(®ion_space_inter_region_bitmap_, visitor);
} else {
DCHECK(space == heap_->non_moving_space_);
non_moving_space_inter_region_bitmap_.VisitMarkedRange( reinterpret_cast<uintptr_t>(space->Begin()), reinterpret_cast<uintptr_t>(space->End()),
visitor);
}
}
} // Done scanning unevac space.
done_scanning_.store(true, std::memory_order_release); // NOTE: inter-region-ref bitmaps can be cleared here to release memory, if needed. // Currently we do it in ReclaimPhase(). if (kVerboseMode) {
LOG(INFO) << "GC end of ScanCardsForSpace";
}
}
{ // For a sticky-bit collection, this phase needs to be after the card scanning since the // mutator may read an unevac space object out of an image object. If the image object is no // longer gray it will trigger a read barrier for the unevac space object.
TimingLogger::ScopedTiming split2("ScanImmuneSpaces", GetTimings()); for (auto& space : immune_spaces_.GetSpaces()) {
DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
ImmuneSpaceScanObjVisitor visitor(this); if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects && table != nullptr) {
table->VisitObjects(ImmuneSpaceScanObjVisitor::Callback, &visitor);
} else {
WriterMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
card_table->Scan<false>(
live_bitmap,
space->Begin(),
space->Limit(),
visitor,
accounting::CardTable::kCardDirty - 1);
}
}
} if (kUseBakerReadBarrier) { // This release fence makes the field updates in the above loop visible before allowing mutator // getting access to immune objects without graying it first.
updated_all_immune_objects_.store(true, std::memory_order_release); // Now "un-gray" (conceptually blacken) immune objects concurrently accessed and grayed by // mutators. We can't do this in the above loop because we would incorrectly disable the read // barrier by un-graying (conceptually blackening) an object which may point to an unscanned, // white object, breaking the to-space invariant (a mutator shall never observe a from-space // (white) object). // // Make sure no mutators are in the middle of marking an immune object before un-graying // (blackening) immune objects.
IssueEmptyCheckpoint();
MutexLock mu(Thread::Current(), immune_gray_stack_lock_); if (kVerboseMode) {
LOG(INFO) << "immune gray stack size=" << immune_gray_stack_.size();
} for (mirror::Object* obj : immune_gray_stack_) {
DCHECK_EQ(obj->GetReadBarrierState(), ReadBarrier::GrayState()); bool success = obj->AtomicSetReadBarrierState(ReadBarrier::GrayState(),
ReadBarrier::NonGrayState());
DCHECK(success);
}
immune_gray_stack_.clear();
}
{
TimingLogger::ScopedTiming split2("VisitConcurrentRoots", GetTimings());
Runtime::Current()->VisitConcurrentRoots(this, kVisitRootFlagAllRoots);
}
{ // TODO: don't visit the transaction roots if it's not active.
TimingLogger::ScopedTiming split5("VisitNonThreadRoots", GetTimings());
Runtime::Current()->VisitNonThreadRoots(this);
}
{
TimingLogger::ScopedTiming split7("Process mark stacks and References", GetTimings());
// Process the mark stack once in the thread local stack mode. This marks most of the live // objects, aside from weak ref accesses with read barriers (Reference::GetReferent() and // system weaks) that may happen concurrently while we are processing the mark stack and newly // mark/gray objects and push refs on the mark stack.
ProcessMarkStack();
ReferenceProcessor* rp = GetHeap()->GetReferenceProcessor(); bool clear_soft_references = GetCurrentIteration()->GetClearSoftReferences();
rp->Setup(self, this, /*concurrent=*/ true, clear_soft_references); if (!clear_soft_references) { // Forward as many SoftReferences as possible before inhibiting reference access.
rp->ForwardSoftReferences(GetTimings());
}
ScopedPriorityChange spc(self); // Make sure we are at a reasonable priority before blocking weak reference access.
spc.SetToNormalOrBetter();
// We transition through three mark stack modes (thread-local, shared, GC-exclusive). The // primary reasons are that we need to use a checkpoint to process thread-local mark // stacks, but after we disable weak refs accesses, we can't use a checkpoint due to a deadlock // issue because running threads potentially blocking at WaitHoldingLocks, and that once we // reach the point where we process weak references, we can avoid using a lock when accessing // the GC mark stack, which makes mark stack processing more efficient.
// Switch to the shared mark stack mode. That is, revoke and process thread-local mark stacks // for the last time before transitioning to the shared mark stack mode, which would process new // refs that may have been concurrently pushed onto the mark stack during the ProcessMarkStack() // call above. At the same time, disable weak ref accesses using a per-thread flag. It's // important to do these together so that we can ensure that mutators won't // newly gray objects and push new refs onto the mark stack due to weak ref accesses and // mutators safely transition to the shared mark stack mode (without leaving unprocessed refs on // the thread-local mark stacks), without a race. This is why we use a thread-local weak ref // access flag Thread::tls32_.weak_ref_access_enabled_ instead of the global ones. // We must use a stop-the-world pause to disable weak ref access. A checkpoint may lead to a // deadlock if one mutator acquires a low-level mutex and then gets blocked while accessing // a weak-ref (after participating in the checkpoint), and another mutator indefinitely waits // for the mutex before it participates in the checkpoint. Consequently, the gc-thread blocks // forever as the checkpoint never finishes (See runtime/mutator_gc_coord.md).
SwitchToSharedMarkStackMode();
CHECK(!self->GetWeakRefAccessEnabled());
// Now that weak refs accesses are disabled, once we exhaust the shared mark stack again here // (which may be non-empty if there were refs found on thread-local mark stacks during the above // SwitchToSharedMarkStackMode() call), we won't have new refs to process, that is, mutators // (via read barriers) have no way to produce any more refs to process. Marking converges once // before we process weak refs below.
ProcessMarkStack();
CheckEmptyMarkStack();
// Switch to the GC exclusive mark stack mode so that we can process the mark stack without a // lock from this point on.
SwitchToGcExclusiveMarkStackMode();
CheckEmptyMarkStack(); if (kVerboseMode) {
LOG(INFO) << "ProcessReferences";
} // Process weak references. This also marks through finalizers. Although // reference processing is "disabled", some accesses will proceed once we've ensured that // objects directly reachable by the mutator are marked, i.e. before we mark through // finalizers.
ProcessReferences(self);
CheckEmptyMarkStack(); // JNI WeakGlobalRefs and most other system weaks cannot be processed until we're done marking // through finalizers, since such references to finalizer-reachable objects must be preserved. if (kVerboseMode) {
LOG(INFO) << "SweepSystemWeaks";
}
SweepSystemWeaks(self);
CheckEmptyMarkStack();
ReenableWeakRefAccess(self); if (kVerboseMode) {
LOG(INFO) << "SweepSystemWeaks done";
} // Marking is done. Disable marking.
DisableMarking();
CheckEmptyMarkStack();
}
if (kIsDebugBuild) {
MutexLock mu(self, *Locks::thread_list_lock_);
CHECK(weak_ref_access_enabled_);
} if (kVerboseMode) {
LOG(INFO) << "GC end of CopyingPhase";
}
}
void ConcurrentCopying::ReenableWeakRefAccess(Thread* self) { if (kVerboseMode) {
LOG(INFO) << "ReenableWeakRefAccess";
} // Iterate all threads (don't need to or can't use a checkpoint) and re-enable weak ref access.
{
MutexLock mu(self, *Locks::thread_list_lock_);
weak_ref_access_enabled_ = true; // This is for new threads.
std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); for (Thread* thread : thread_list) {
thread->SetWeakRefAccessEnabled(true);
}
} // Unblock blocking threads.
GetHeap()->GetReferenceProcessor()->BroadcastForSlowPath(self);
Runtime::Current()->BroadcastForNewSystemWeaks();
}
class ConcurrentCopying::DisableMarkingCheckpoint : public Closure { public: explicit DisableMarkingCheckpoint(ConcurrentCopying* concurrent_copying)
: concurrent_copying_(concurrent_copying) {
}
void Run(Thread* thread) override NO_THREAD_SAFETY_ANALYSIS { // Note: self is not necessarily equal to thread since thread may be suspended.
Thread* self = Thread::Current();
DCHECK(thread == self ||
thread->IsSuspended() ||
thread->GetState() == ThreadState::kWaitingPerformingGc)
<< thread->GetState() << " thread " << thread << " self " << self;
thread->GetInterpreterCache()->Clear(thread); // Disable the thread-local is_gc_marking flag. // Note a thread that has just started right before this checkpoint may have already this flag // set to false, which is ok.
thread->SetIsGcMarkingAndUpdateEntrypoints(false); // If thread is a running mutator, then act on behalf of the garbage collector. // See the code in ThreadList::RunCheckpoint.
concurrent_copying_->GetBarrier().Pass(self);
}
class ConcurrentCopying::DisableMarkingCallback : public Closure { public: explicit DisableMarkingCallback(ConcurrentCopying* concurrent_copying)
: concurrent_copying_(concurrent_copying) {
}
void Run([[maybe_unused]] Thread* self) override REQUIRES(Locks::thread_list_lock_) { // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint() // to avoid a race with ThreadList::Register().
CHECK(concurrent_copying_->is_marking_);
concurrent_copying_->is_marking_ = false;
concurrent_copying_->GetCurrentIteration()->SetAppSlowPathDurationMs(
MilliTime() - concurrent_copying_->app_slow_path_start_time_); if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) {
CHECK(concurrent_copying_->is_using_read_barrier_entrypoints_);
concurrent_copying_->is_using_read_barrier_entrypoints_ = false;
} else {
CHECK(!concurrent_copying_->is_using_read_barrier_entrypoints_);
}
}
void ConcurrentCopying::IssueDisableMarkingCheckpoint() {
Thread* self = Thread::Current();
DisableMarkingCheckpoint check_point(this);
ThreadList* thread_list = Runtime::Current()->GetThreadList();
gc_barrier_->Init(self, 0);
DisableMarkingCallback dmc(this);
size_t barrier_count = thread_list->RunCheckpoint(&check_point, &dmc); // If there are no threads to wait which implies that all the checkpoint functions are finished, // then no need to release the mutator lock. if (barrier_count == 0) { return;
} // Release locks then wait for all mutator threads to pass the barrier.
Locks::mutator_lock_->SharedUnlock(self);
{
ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
gc_barrier_->Increment(self, barrier_count);
}
Locks::mutator_lock_->SharedLock(self);
}
void ConcurrentCopying::DisableMarking() { // Use a checkpoint to turn off the global is_marking and the thread-local is_gc_marking flags and // to ensure no threads are still in the middle of a read barrier which may have a from-space ref // cached in a local variable.
IssueDisableMarkingCheckpoint(); if (kUseTableLookupReadBarrier) {
heap_->rb_table_->ClearAll();
DCHECK(heap_->rb_table_->IsAllCleared());
} if (kIsDebugBuild) {
is_mark_stack_push_disallowed_.store(1, std::memory_order_relaxed);
}
mark_stack_mode_.store(kMarkStackModeOff, std::memory_order_release);
}
void ConcurrentCopying::IssueEmptyCheckpoint() {
Thread* self = Thread::Current();
ThreadList* thread_list = Runtime::Current()->GetThreadList(); // Release locks then wait for all mutator threads to pass the barrier.
Locks::mutator_lock_->SharedUnlock(self);
thread_list->RunEmptyCheckpoint();
Locks::mutator_lock_->SharedLock(self);
}
// The following visitors are used to verify that there's no references to the from-space left after // marking. class ConcurrentCopying::VerifyNoFromSpaceRefsVisitor : public SingleRootVisitor { public: explicit VerifyNoFromSpaceRefsVisitor(ConcurrentCopying* collector)
: collector_(collector) {}
// Verify there's no from-space references left after the marking phase. void ConcurrentCopying::VerifyNoFromSpaceReferences() {
Thread* self = Thread::Current();
DCHECK(Locks::mutator_lock_->IsExclusiveHeld(self)); // Verify all threads have is_gc_marking to be false
{
MutexLock mu(self, *Locks::thread_list_lock_);
std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); for (Thread* thread : thread_list) {
CHECK(!thread->GetIsGcMarking());
}
}
auto verify_no_from_space_refs_visitor = [&](mirror::Object* obj)
REQUIRES_SHARED(Locks::mutator_lock_) {
CHECK(obj != nullptr);
space::RegionSpace* region_space = RegionSpace();
CHECK(!region_space->IsInFromSpace(obj)) << "Scanning object " << obj << " in from space";
VerifyNoFromSpaceRefsFieldVisitor visitor(this);
obj->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
visitor,
visitor); if (kUseBakerReadBarrier) {
CHECK_EQ(obj->GetReadBarrierState(), ReadBarrier::NonGrayState())
<< "obj=" << obj << " has gray rb_state " << obj->GetReadBarrierState();
}
}; // Roots.
{
ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
VerifyNoFromSpaceRefsVisitor ref_visitor(this);
Runtime::Current()->VisitRoots(&ref_visitor);
} // The to-space.
region_space_->WalkToSpace(verify_no_from_space_refs_visitor); // Non-moving spaces.
{
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
heap_->GetMarkBitmap()->Visit(verify_no_from_space_refs_visitor);
} // The alloc stack.
{
VerifyNoFromSpaceRefsVisitor ref_visitor(this); for (auto* it = heap_->allocation_stack_->Begin(), *end = heap_->allocation_stack_->End();
it < end; ++it) {
mirror::Object* const obj = it->AsMirrorPtr(); if (obj != nullptr && obj->GetClass() != nullptr) { // TODO: need to call this only if obj is alive?
ref_visitor(obj);
verify_no_from_space_refs_visitor(obj);
}
}
} // TODO: LOS. But only refs in LOS are classes.
}
// The following visitors are used to assert the to-space invariant. class ConcurrentCopying::AssertToSpaceInvariantFieldVisitor { public: explicit AssertToSpaceInvariantFieldVisitor(ConcurrentCopying* collector)
: collector_(collector) {}
void ConcurrentCopying::RevokeThreadLocalMarkStacks(bool disable_weak_ref_access,
Closure* checkpoint_callback) {
Thread* self = Thread::Current();
Locks::mutator_lock_->AssertSharedHeld(self);
ThreadList* thread_list = Runtime::Current()->GetThreadList();
RevokeThreadLocalMarkStackCheckpoint check_point(this, disable_weak_ref_access); if (disable_weak_ref_access) { // We're the only thread that could possibly ask for exclusive access here.
Locks::mutator_lock_->SharedUnlock(self);
{
ScopedPause pause(this);
MutexLock mu(self, *Locks::thread_list_lock_);
checkpoint_callback->Run(self); for (Thread* thread : thread_list->GetList()) {
check_point.Run(thread);
}
}
Locks::mutator_lock_->SharedLock(self);
} else {
gc_barrier_->Init(self, 0);
size_t barrier_count = thread_list->RunCheckpoint(&check_point, checkpoint_callback); // If there are no threads to wait which implys that all the checkpoint functions are finished, // then no need to release the mutator lock. if (barrier_count == 0) { return;
}
Locks::mutator_lock_->SharedUnlock(self);
{
ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
gc_barrier_->Increment(self, barrier_count);
}
Locks::mutator_lock_->SharedLock(self);
}
}
void ConcurrentCopying::ProcessMarkStack() { if (kVerboseMode) {
LOG(INFO) << "ProcessMarkStack. ";
} bool empty_prev = false; while (true) { bool empty = ProcessMarkStackOnce(); if (empty_prev && empty) { // Saw empty mark stack for a second time, done. break;
}
empty_prev = empty;
}
}
bool ConcurrentCopying::ProcessMarkStackOnce() {
DCHECK(thread_running_gc_ != nullptr);
Thread* const self = Thread::Current();
DCHECK(self == thread_running_gc_);
DCHECK(thread_running_gc_->GetThreadLocalMarkStack() == nullptr);
size_t count = 0;
MarkStackMode mark_stack_mode = mark_stack_mode_.load(std::memory_order_acquire); if (mark_stack_mode == kMarkStackModeThreadLocal) { // Process the thread-local mark stacks and the GC mark stack.
count += ProcessThreadLocalMarkStacks(/* disable_weak_ref_access= */ false, /* checkpoint_callback= */ nullptr,
[this] (mirror::Object* ref)
REQUIRES_SHARED(Locks::mutator_lock_) {
ProcessMarkStackRef(ref);
}); while (!gc_mark_stack_->IsEmpty()) {
mirror::Object* to_ref = gc_mark_stack_->PopBack();
ProcessMarkStackRef(to_ref);
++count;
}
gc_mark_stack_->Reset();
} elseif (mark_stack_mode == kMarkStackModeShared) { // Do an empty checkpoint to avoid a race with a mutator preempted in the middle of a read // barrier but before pushing onto the mark stack. b/32508093. Note the weak ref access is // disabled at this point.
IssueEmptyCheckpoint(); // Process the shared GC mark stack with a lock.
{
MutexLock mu(thread_running_gc_, mark_stack_lock_);
CHECK(revoked_mark_stacks_.empty());
CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
} while (true) {
std::vector<mirror::Object*> refs;
{ // Copy refs with lock. Note the number of refs should be small.
MutexLock mu(thread_running_gc_, mark_stack_lock_); if (gc_mark_stack_->IsEmpty()) { break;
} for (StackReference<mirror::Object>* p = gc_mark_stack_->Begin();
p != gc_mark_stack_->End(); ++p) {
refs.push_back(p->AsMirrorPtr());
}
gc_mark_stack_->Reset();
} for (mirror::Object* ref : refs) {
ProcessMarkStackRef(ref);
++count;
}
}
} else {
CHECK_EQ(static_cast<uint32_t>(mark_stack_mode), static_cast<uint32_t>(kMarkStackModeGcExclusive));
{
MutexLock mu(thread_running_gc_, mark_stack_lock_);
CHECK(revoked_mark_stacks_.empty());
CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
} // Process the GC mark stack in the exclusive mode. No need to take the lock. while (!gc_mark_stack_->IsEmpty()) {
mirror::Object* to_ref = gc_mark_stack_->PopBack();
ProcessMarkStackRef(to_ref);
++count;
}
gc_mark_stack_->Reset();
}
// Return true if the stack was empty. return count == 0;
}
template <typename Processor>
size_t ConcurrentCopying::ProcessThreadLocalMarkStacks(bool disable_weak_ref_access,
Closure* checkpoint_callback, const Processor& processor) { // Run a checkpoint to collect all thread local mark stacks and iterate over them all.
RevokeThreadLocalMarkStacks(disable_weak_ref_access, checkpoint_callback); if (disable_weak_ref_access) {
CHECK_EQ(static_cast<uint32_t>(mark_stack_mode_.load(std::memory_order_relaxed)), static_cast<uint32_t>(kMarkStackModeShared));
}
size_t count = 0;
std::vector<accounting::AtomicStack<mirror::Object>*> mark_stacks;
{
MutexLock mu(thread_running_gc_, mark_stack_lock_); // Make a copy of the mark stack vector.
mark_stacks = revoked_mark_stacks_;
revoked_mark_stacks_.clear();
} for (accounting::AtomicStack<mirror::Object>* mark_stack : mark_stacks) { for (StackReference<mirror::Object>* p = mark_stack->Begin(); p != mark_stack->End(); ++p) {
mirror::Object* to_ref = p->AsMirrorPtr();
processor(to_ref);
++count;
}
{
MutexLock mu(thread_running_gc_, mark_stack_lock_); if (pooled_mark_stacks_.size() >= kMarkStackPoolSize) { // The pool has enough. Delete it. delete mark_stack;
} else { // Otherwise, put it into the pool for later reuse.
mark_stack->Reset();
pooled_mark_stacks_.push_back(mark_stack);
}
}
} if (disable_weak_ref_access) {
MutexLock mu(thread_running_gc_, mark_stack_lock_);
CHECK(revoked_mark_stacks_.empty());
CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
} return count;
}
void ConcurrentCopying::VerifyLargeObject(mirror::Object* ref,
mirror::Object* holder,
MemberOffset offset) { auto* los = heap_->GetLargeObjectsSpace(); if (los == nullptr || !IsAlignedParam(ref, space::LargeObjectSpace::ObjectAlignment())) { if (los == nullptr) {
LOG(FATAL_WITHOUT_ABORT)
<< "ref=" << ref
<< " doesn't belong to non-moving space and large object space doesn't exist";
} // Ref is not aligned as per large-object-space, it must be heap corruption.
region_space_->Unprotect();
heap_->GetVerification()->LogHeapCorruption(holder, offset, ref, /*fatal=*/true);
}
}
inlinevoid ConcurrentCopying::ProcessMarkStackRef(mirror::Object* to_ref) {
DCHECK(!region_space_->IsInFromSpace(to_ref));
size_t obj_size = 0;
space::RegionSpace::RegionType rtype = region_space_->GetRegionType(to_ref); if (kUseBakerReadBarrier) {
DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState())
<< " to_ref=" << to_ref
<< " rb_state=" << to_ref->GetReadBarrierState()
<< " is_marked=" << IsMarked(to_ref)
<< " type=" << to_ref->PrettyTypeOf()
<< " young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha
<< " space=" << heap_->DumpSpaceNameFromAddress(to_ref)
<< " region_type=" << rtype;
} bool add_to_live_bytes = false; // Invariant: There should be no object from a newly-allocated // region (either large or non-large) on the mark stack.
DCHECK(!region_space_->IsInNewlyAllocatedRegion(to_ref)) << to_ref; bool perform_scan = false; switch (rtype) { case space::RegionSpace::RegionType::kRegionTypeUnevacFromSpace: // Mark the bitmap only in the GC thread here so that we don't need a CAS. if (!kUseBakerReadBarrier || !region_space_bitmap_->Set(to_ref)) { // It may be already marked if we accidentally pushed the same object twice due to the racy // bitmap read in MarkUnevacFromSpaceRegion. if (use_generational_cc_ && young_gen_) {
CHECK(region_space_->IsLargeObject(to_ref));
region_space_->ZeroLiveBytesForLargeObject(to_ref);
}
perform_scan = true; // Only add to the live bytes if the object was not already marked and we are not the young // GC. // Why add live bytes even after 2-phase GC? // We need to ensure that if there is a unevac region with any live // objects, then its live_bytes must be non-zero. Otherwise, // ClearFromSpace() will clear the region. Considering, that we may skip // live objects during marking phase of 2-phase GC, we have to take care // of such objects here.
add_to_live_bytes = true;
} break; case space::RegionSpace::RegionType::kRegionTypeToSpace: if (use_generational_cc_) { // Copied to to-space, set the bit so that the next GC can scan objects.
region_space_bitmap_->Set(to_ref);
}
perform_scan = true; break; default:
DCHECK(!region_space_->HasAddress(to_ref)) << to_ref;
DCHECK(!immune_spaces_.ContainsObject(to_ref)); // Non-moving or large-object space. if (kUseBakerReadBarrier) {
accounting::ContinuousSpaceBitmap* mark_bitmap =
heap_->GetNonMovingSpace()->GetMarkBitmap(); if (!mark_bitmap->HasAddress(to_ref)) {
VerifyLargeObject(to_ref, /*holder=*/nullptr, MemberOffset(0));
accounting::LargeObjectBitmap* los_bitmap =
heap_->GetLargeObjectsSpace()->GetMarkBitmap();
DCHECK(los_bitmap->HasAddress(to_ref)); // Only the GC thread could be setting the LOS bit map hence doesn't // need to be atomically done.
perform_scan = !los_bitmap->Set(to_ref);
} else { // Only the GC thread could be setting the non-moving space bit map // hence doesn't need to be atomically done.
perform_scan = !mark_bitmap->Set(to_ref);
}
} else {
perform_scan = true;
}
} if (perform_scan) {
obj_size = to_ref->SizeOf<kDefaultVerifyFlags>(); if (use_generational_cc_ && young_gen_) {
Scan<true>(to_ref, obj_size);
} else {
Scan<false>(to_ref, obj_size);
}
} if (kUseBakerReadBarrier) {
DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState())
<< " to_ref=" << to_ref
<< " rb_state=" << to_ref->GetReadBarrierState()
<< " is_marked=" << IsMarked(to_ref)
<< " type=" << to_ref->PrettyTypeOf()
<< " young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha
<< " space=" << heap_->DumpSpaceNameFromAddress(to_ref)
<< " region_type=" << rtype // TODO: Temporary; remove this when this is no longer needed (b/116087961).
<< " runtime->sentinel=" << Runtime::Current()->GetSentinel().Read<kWithoutReadBarrier>();
} #ifdef USE_BAKER_READ_BARRIER
mirror::Object* referent = nullptr; if (UNLIKELY((to_ref->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass() &&
(referent = to_ref->AsReference()->GetReferent<kWithoutReadBarrier>()) != nullptr &&
!IsInToSpace(referent)))) { // Leave this reference gray in the queue so that GetReferent() will trigger a read barrier. We // will change it to non-gray later in ReferenceQueue::DisableReadBarrierForReference.
DCHECK(to_ref->AsReference()->GetPendingNext() != nullptr)
<< "Left unenqueued ref gray " << to_ref;
} else { // We may occasionally leave a reference non-gray in the queue if its referent happens to be // concurrently marked after the Scan() call above has enqueued the Reference, in which case the // above IsInToSpace() evaluates to true and we change the color from gray to non-gray here in // this else block. if (kUseBakerReadBarrier) { bool success = to_ref->AtomicSetReadBarrierState(
ReadBarrier::GrayState(), ReadBarrier::NonGrayState(), std::memory_order_release);
DCHECK(success) << "Must succeed as we won the race.";
}
} #else
DCHECK(!kUseBakerReadBarrier); #endif
if (add_to_live_bytes) { // Add to the live bytes per unevacuated from-space. Note this code is always run by the // GC-running thread (no synchronization required).
DCHECK(region_space_bitmap_->Test(to_ref)); if (obj_size == 0) {
obj_size = to_ref->SizeOf<kDefaultVerifyFlags>();
}
region_space_->AddLiveBytes(to_ref, RoundUp(obj_size, space::RegionSpace::kAlignment));
} if (ReadBarrier::kEnableToSpaceInvariantChecks) {
CHECK(to_ref != nullptr);
space::RegionSpace* region_space = RegionSpace();
CHECK(!region_space->IsInFromSpace(to_ref)) << "Scanning object " << to_ref << " in from space";
AssertToSpaceInvariant(nullptr, MemberOffset(0), to_ref);
AssertToSpaceInvariantFieldVisitor visitor(this);
to_ref->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
visitor,
visitor);
}
}
class ConcurrentCopying::DisableWeakRefAccessCallback : public Closure { public: explicit DisableWeakRefAccessCallback(ConcurrentCopying* concurrent_copying)
: concurrent_copying_(concurrent_copying) {
}
void Run([[maybe_unused]] Thread* self) override REQUIRES(Locks::thread_list_lock_) { // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint() // to avoid a deadlock b/31500969.
CHECK(concurrent_copying_->weak_ref_access_enabled_);
concurrent_copying_->weak_ref_access_enabled_ = false;
}
void ConcurrentCopying::SwitchToSharedMarkStackMode() {
Thread* self = Thread::Current();
DCHECK(thread_running_gc_ != nullptr);
DCHECK(self == thread_running_gc_);
DCHECK(thread_running_gc_->GetThreadLocalMarkStack() == nullptr);
CHECK_EQ(static_cast<uint32_t>(mark_stack_mode_.load(std::memory_order_relaxed)), static_cast<uint32_t>(kMarkStackModeThreadLocal));
mark_stack_mode_.store(kMarkStackModeShared, std::memory_order_release);
DisableWeakRefAccessCallback dwrac(this); // Process the thread local mark stacks one last time after switching to the shared mark stack // mode and disable weak ref accesses.
ProcessThreadLocalMarkStacks(/* disable_weak_ref_access= */ true,
&dwrac,
[this] (mirror::Object* ref)
REQUIRES_SHARED(Locks::mutator_lock_) {
ProcessMarkStackRef(ref);
}); if (kVerboseMode) {
LOG(INFO) << "Switched to shared mark stack mode and disabled weak ref access";
}
}
void ConcurrentCopying::Sweep(bool swap_bitmaps) { if (use_generational_cc_ && young_gen_) { // Only sweep objects on the live stack.
SweepArray(heap_->GetLiveStack(), /* swap_bitmaps= */ false);
} else {
{
TimingLogger::ScopedTiming t("MarkStackAsLive", GetTimings());
accounting::ObjectStack* live_stack = heap_->GetLiveStack(); if (kEnableFromSpaceAccountingCheck) { // Ensure that nobody inserted items in the live stack after we swapped the stacks.
CHECK_GE(live_stack_freeze_size_, live_stack->Size());
}
heap_->MarkAllocStackAsLive(live_stack);
live_stack->Reset();
}
CheckEmptyMarkStack();
TimingLogger::ScopedTiming split("Sweep", GetTimings()); for (constauto& space : GetHeap()->GetContinuousSpaces()) { if (space->IsContinuousMemMapAllocSpace() && space != region_space_
&& !immune_spaces_.ContainsSpace(space)) {
space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
TimingLogger::ScopedTiming split2(
alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings());
RecordFree(alloc_space->Sweep(swap_bitmaps));
}
}
SweepLargeObjects(swap_bitmaps);
}
}
void ConcurrentCopying::SweepArray(accounting::ObjectStack* obj_arr, bool swap_bitmaps) { // This method is only used when Generational CC collection is enabled.
DCHECK(use_generational_cc_);
CheckEmptyMarkStack();
TimingLogger::ScopedTiming t("SweepArray", GetTimings());
std::vector<space::ContinuousSpace*> sweep_spaces; for (space::ContinuousSpace* space : heap_->GetContinuousSpaces()) { if (!space->IsAllocSpace() ||
space == region_space_ ||
immune_spaces_.ContainsSpace(space) ||
space->GetLiveBitmap() == nullptr) { continue;
}
sweep_spaces.push_back(space);
}
GarbageCollector::SweepArray(obj_arr, swap_bitmaps, &sweep_spaces);
}
void ConcurrentCopying::MarkZygoteLargeObjects() {
TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings());
Thread* const self = Thread::Current();
WriterMutexLock rmu(self, *Locks::heap_bitmap_lock_);
space::LargeObjectSpace* const los = heap_->GetLargeObjectsSpace(); if (los != nullptr) { // Pick the current live bitmap (mark bitmap if swapped).
accounting::LargeObjectBitmap* const live_bitmap = los->GetLiveBitmap();
accounting::LargeObjectBitmap* const mark_bitmap = los->GetMarkBitmap(); // Walk through all of the objects and explicitly mark the zygote ones so they don't get swept.
std::pair<uint8_t*, uint8_t*> range = los->GetBeginEndAtomic();
live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(range.first), reinterpret_cast<uintptr_t>(range.second),
[mark_bitmap, los, self](mirror::Object* obj)
REQUIRES(Locks::heap_bitmap_lock_)
REQUIRES_SHARED(Locks::mutator_lock_) { if (los->IsZygoteLargeObject(self, obj)) {
mark_bitmap->Set(obj);
}
});
}
}
void ConcurrentCopying::CaptureRssAtPeak() { using range_t = std::pair<void*, void*>; // This operation is expensive as several calls to mincore() are performed. // Also, this must be called before clearing regions in ReclaimPhase(). // Therefore, we make it conditional on the flag that enables dumping GC // performance info on shutdown. if (Runtime::Current()->GetDumpGCPerformanceOnShutdown()) {
std::list<range_t> gc_ranges; auto add_gc_range = [&gc_ranges](void* start, size_t size) { void* end = static_cast<char*>(start) + RoundUp(size, gPageSize);
gc_ranges.emplace_back(range_t(start, end));
};
// region space
DCHECK(IsAlignedParam(region_space_->Limit(), gPageSize));
gc_ranges.emplace_back(range_t(region_space_->Begin(), region_space_->Limit())); // mark bitmap
add_gc_range(region_space_bitmap_->Begin(), region_space_bitmap_->Size());
// non-moving space
{
DCHECK(IsAlignedParam(heap_->non_moving_space_->Limit(), gPageSize));
gc_ranges.emplace_back(range_t(heap_->non_moving_space_->Begin(),
heap_->non_moving_space_->Limit())); // mark bitmap
accounting::ContinuousSpaceBitmap *bitmap = heap_->non_moving_space_->GetMarkBitmap();
add_gc_range(bitmap->Begin(), bitmap->Size()); // live bitmap. Deal with bound bitmaps.
ReaderMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_); if (heap_->non_moving_space_->HasBoundBitmaps()) {
DCHECK_EQ(bitmap->Begin(),
heap_->non_moving_space_->GetLiveBitmap()->Begin());
bitmap = heap_->non_moving_space_->GetTempBitmap();
} else {
bitmap = heap_->non_moving_space_->GetLiveBitmap();
}
add_gc_range(bitmap->Begin(), bitmap->Size());
} // large-object space if (heap_->GetLargeObjectsSpace()) {
heap_->GetLargeObjectsSpace()->ForEachMemMap([&add_gc_range](const MemMap& map) {
DCHECK(IsAlignedParam(map.BaseSize(), gPageSize));
add_gc_range(map.BaseBegin(), map.BaseSize());
}); // mark bitmap
accounting::LargeObjectBitmap* bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
add_gc_range(bitmap->Begin(), bitmap->Size()); // live bitmap
bitmap = heap_->GetLargeObjectsSpace()->GetLiveBitmap();
add_gc_range(bitmap->Begin(), bitmap->Size());
} // card table
add_gc_range(heap_->GetCardTable()->MemMapBegin(), heap_->GetCardTable()->MemMapSize()); // inter-region refs if (use_generational_cc_ && !young_gen_) { // region space
add_gc_range(region_space_inter_region_bitmap_.Begin(),
region_space_inter_region_bitmap_.Size()); // non-moving space
add_gc_range(non_moving_space_inter_region_bitmap_.Begin(),
non_moving_space_inter_region_bitmap_.Size());
} // Extract RSS using mincore(). Updates the cummulative RSS counter.
ExtractRssFromMincore(&gc_ranges);
}
}
// Free data for class loaders that we unloaded. This includes removing // dead methods from JIT's internal maps. This must be done before // reclaiming the memory of the dead methods' declaring classes.
Runtime::Current()->GetClassLinker()->CleanupClassLoaders();
{ // Double-check that the mark stack is empty. // Note: need to set this after VerifyNoFromSpaceRef().
is_asserting_to_space_invariant_ = false;
QuasiAtomic::ThreadFenceForConstructor(); // TODO: Remove? if (kVerboseMode) {
LOG(INFO) << "Issue an empty check point. ";
}
IssueEmptyCheckpoint(); // Disable the check. if (kIsDebugBuild) {
is_mark_stack_push_disallowed_.store(0, std::memory_order_relaxed);
} if (kUseBakerReadBarrier) {
updated_all_immune_objects_.store(false, std::memory_order_seq_cst);
}
CheckEmptyMarkStack();
}
// Capture RSS at the time when memory usage is at its peak. All GC related // memory ranges like java heap, card table, bitmap etc. are taken into // account. // TODO: We can fetch resident memory for region space directly by going // through list of allocated regions. This way we can avoid calling mincore on // the biggest memory range, thereby reducing the cost of this function.
CaptureRssAtPeak();
// Sweep the malloc spaces before clearing the from space since the memory tool mode might // access the object classes in the from space for dead objects.
{
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
Sweep(/* swap_bitmaps= */ false);
SwapBitmaps();
heap_->UnBindBitmaps();
// The bitmap was cleared at the start of the GC, there is nothing we need to do here.
DCHECK(region_space_bitmap_ != nullptr);
region_space_bitmap_ = nullptr;
}
{ // Record freed objects.
TimingLogger::ScopedTiming split2("RecordFree", GetTimings()); // Don't include thread-locals that are in the to-space. const uint64_t from_bytes = region_space_->GetBytesAllocatedInFromSpace(); const uint64_t unevac_from_bytes = region_space_->GetBytesAllocatedInUnevacFromSpace();
uint64_t to_bytes = bytes_moved_.load(std::memory_order_relaxed) + bytes_moved_gc_thread_;
cumulative_bytes_moved_ += to_bytes;
uint64_t to_objects = objects_moved_.load(std::memory_order_relaxed) + objects_moved_gc_thread_; if (kEnableFromSpaceAccountingCheck) {
CHECK_EQ(from_space_num_bytes_at_first_pause_, from_bytes + unevac_from_bytes);
} // to_bytes <= from_bytes is only approximately true, because objects expand a little when // copying to non-moving space in near-OOM situations. if (from_bytes > 0) {
copied_live_bytes_ratio_sum_ += static_cast<float>(to_bytes) / from_bytes;
gc_count_++;
}
// Cleared bytes and objects, populated by the call to RegionSpace::ClearFromSpace below.
uint64_t cleared_bytes;
uint64_t cleared_objects; bool should_eagerly_release_memory = ShouldEagerlyReleaseMemoryToOS();
{
TimingLogger::ScopedTiming split4("ClearFromSpace", GetTimings());
region_space_->ClearFromSpace(&cleared_bytes,
&cleared_objects, /*clear_bitmap*/ !young_gen_,
should_eagerly_release_memory); // `cleared_bytes` may be greater than the from space equivalents since // RegionSpace::ClearFromSpace may clear empty unevac regions.
CHECK_GE(cleared_bytes, from_bytes);
}
// If we need to release available memory to the OS, go over all free // regions which the kernel might still cache. if (should_eagerly_release_memory) {
TimingLogger::ScopedTiming split4("Release free regions", GetTimings());
region_space_->ReleaseFreeRegions();
}
// freed_bytes could conceivably be negative if we fall back to nonmoving space and have to // pad to a larger size.
int64_t freed_bytes = (int64_t)cleared_bytes - (int64_t)to_bytes;
uint64_t freed_objects = cleared_objects - to_objects; if (kVerboseMode) {
LOG(INFO) << "RecordFree:"
<< " from_bytes=" << from_bytes
<< " unevac_from_bytes=" << unevac_from_bytes
<< " to_bytes=" << to_bytes
<< " freed_bytes=" << freed_bytes
<< " from_space size=" << region_space_->FromSpaceSize()
<< " unevac_from_space size=" << region_space_->UnevacFromSpaceSize()
<< " to_space size=" << region_space_->ToSpaceSize();
LOG(INFO) << "(before) num_bytes_allocated="
<< heap_->num_bytes_allocated_.load();
}
RecordFree(ObjectBytePair(freed_objects, freed_bytes));
GetCurrentIteration()->SetScannedBytes(bytes_scanned_); if (kVerboseMode) {
LOG(INFO) << "(after) num_bytes_allocated="
<< heap_->num_bytes_allocated_.load();
}
void ConcurrentCopying::AssertToSpaceInvariant(GcRootSource* gc_root_source,
mirror::Object* ref) {
CHECK_EQ(heap_->collector_type_, kCollectorTypeCC) << static_cast<size_t>(heap_->collector_type_); if (is_asserting_to_space_invariant_) { if (ref == nullptr) { // OK. return;
} elseif (region_space_->HasAddress(ref)) { // Check to-space invariant in region space (moving space). using RegionType = space::RegionSpace::RegionType;
space::RegionSpace::RegionType type = region_space_->GetRegionTypeUnsafe(ref); if (type == RegionType::kRegionTypeToSpace) { // OK. return;
} elseif (type == RegionType::kRegionTypeUnevacFromSpace) { if (!IsMarkedInUnevacFromSpace(ref)) {
LOG(FATAL_WITHOUT_ABORT) << "Found unmarked reference in unevac from-space:"; // Remove memory protection from the region space and log debugging information.
region_space_->Unprotect();
LOG(FATAL_WITHOUT_ABORT) << DumpGcRoot(ref);
}
CHECK(IsMarkedInUnevacFromSpace(ref)) << ref;
} else { // Not OK: either a from-space ref or a reference in an unused region. if (type == RegionType::kRegionTypeFromSpace) {
LOG(FATAL_WITHOUT_ABORT) << "Found from-space reference:";
} else {
LOG(FATAL_WITHOUT_ABORT) << "Found reference in region with type " << type << ":";
} // Remove memory protection from the region space and log debugging information.
region_space_->Unprotect();
LOG(FATAL_WITHOUT_ABORT) << DumpGcRoot(ref); if (gc_root_source == nullptr) { // No info.
} elseif (gc_root_source->HasArtField()) {
ArtField* field = gc_root_source->GetArtField();
LOG(FATAL_WITHOUT_ABORT) << "gc root in field " << field << " "
<< ArtField::PrettyField(field);
RootPrinter root_printer;
field->VisitRoots(root_printer);
} elseif (gc_root_source->HasArtMethod()) {
ArtMethod* method = gc_root_source->GetArtMethod();
LOG(FATAL_WITHOUT_ABORT) << "gc root in method " << method << " "
<< ArtMethod::PrettyMethod(method);
RootPrinter root_printer;
method->VisitRoots(root_printer, kRuntimePointerSize);
}
ref->GetLockWord(false).Dump(LOG_STREAM(FATAL_WITHOUT_ABORT));
LOG(FATAL_WITHOUT_ABORT) << "Non-free regions:";
region_space_->DumpNonFreeRegions(LOG_STREAM(FATAL_WITHOUT_ABORT));
PrintFileToLog("/proc/self/maps", LogSeverity::FATAL_WITHOUT_ABORT);
MemMap::DumpMaps(LOG_STREAM(FATAL_WITHOUT_ABORT), /* terse= */ true);
LOG(FATAL) << "Invalid reference " << ref;
}
} else { // Check to-space invariant in non-moving space.
AssertToSpaceInvariantInNonMovingSpace(/* obj= */ nullptr, ref);
}
}
}
void ConcurrentCopying::LogFromSpaceRefHolder(mirror::Object* obj, MemberOffset offset) { if (kUseBakerReadBarrier) {
LOG(INFO) << "holder=" << obj << " " << obj->PrettyTypeOf()
<< " holder rb_state=" << obj->GetReadBarrierState();
} else {
LOG(INFO) << "holder=" << obj << " " << obj->PrettyTypeOf();
} if (region_space_->IsInFromSpace(obj)) {
LOG(INFO) << "holder is in the from-space.";
} elseif (region_space_->IsInToSpace(obj)) {
LOG(INFO) << "holder is in the to-space.";
} elseif (region_space_->IsInUnevacFromSpace(obj)) {
LOG(INFO) << "holder is in the unevac from-space."; if (IsMarkedInUnevacFromSpace(obj)) {
LOG(INFO) << "holder is marked in the region space bitmap.";
} else {
LOG(INFO) << "holder is not marked in the region space bitmap.";
}
} else { // In a non-moving space. if (immune_spaces_.ContainsObject(obj)) {
LOG(INFO) << "holder is in an immune image or the zygote space.";
} else {
LOG(INFO) << "holder is in a non-immune, non-moving (or main) space.";
accounting::ContinuousSpaceBitmap* mark_bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
accounting::LargeObjectBitmap* los_bitmap = nullptr; constbool is_los = !mark_bitmap->HasAddress(obj); if (is_los) {
DCHECK(heap_->GetLargeObjectsSpace() && heap_->GetLargeObjectsSpace()->Contains(obj))
<< "obj=" << obj
<< " LOS bit map covers the entire lower 4GB address range";
los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
} if (!is_los && mark_bitmap->Test(obj)) {
LOG(INFO) << "holder is marked in the non-moving space mark bit map.";
} elseif (is_los && los_bitmap->Test(obj)) {
LOG(INFO) << "holder is marked in the los bit map.";
} else { // If ref is on the allocation stack, then it is considered // mark/alive (but not necessarily on the live stack.) if (IsOnAllocStack(obj)) {
LOG(INFO) << "holder is on the alloc stack.";
} else {
LOG(INFO) << "holder is not marked or on the alloc stack.";
}
}
}
}
LOG(INFO) << "offset=" << offset.SizeValue();
}
bool ConcurrentCopying::IsMarkedInNonMovingSpace(mirror::Object* from_ref) {
DCHECK(!region_space_->HasAddress(from_ref)) << "ref=" << from_ref;
DCHECK(!immune_spaces_.ContainsObject(from_ref)) << "ref=" << from_ref; if (kUseBakerReadBarrier && from_ref->GetReadBarrierStateAcquire() == ReadBarrier::GrayState()) { returntrue;
} elseif (!use_generational_cc_ || done_scanning_.load(std::memory_order_acquire)) { // Read the comment in IsMarkedInUnevacFromSpace()
accounting::ContinuousSpaceBitmap* mark_bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
accounting::LargeObjectBitmap* los_bitmap = nullptr; constbool is_los = !mark_bitmap->HasAddress(from_ref); if (is_los) {
DCHECK(heap_->GetLargeObjectsSpace() && heap_->GetLargeObjectsSpace()->Contains(from_ref))
<< "ref=" << from_ref
<< " doesn't belong to non-moving space and large object space doesn't exist";
los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
} if (is_los ? los_bitmap->Test(from_ref) : mark_bitmap->Test(from_ref)) { returntrue;
}
} return IsOnAllocStack(from_ref);
}
void ConcurrentCopying::AssertToSpaceInvariantInNonMovingSpace(mirror::Object* obj,
mirror::Object* ref) {
CHECK(ref != nullptr);
CHECK(!region_space_->HasAddress(ref)) << "obj=" << obj << " ref=" << ref; // In a non-moving space. Check that the ref is marked. if (immune_spaces_.ContainsObject(ref)) { // Immune space case. if (kUseBakerReadBarrier) { // Immune object may not be gray if called from the GC. if (Thread::Current() == thread_running_gc_ && !gc_grays_immune_objects_) { return;
} bool updated_all_immune_objects = updated_all_immune_objects_.load(std::memory_order_seq_cst);
CHECK(updated_all_immune_objects || ref->GetReadBarrierState() == ReadBarrier::GrayState())
<< "Unmarked immune space ref. obj=" << obj << " rb_state="
<< (obj != nullptr ? obj->GetReadBarrierState() : 0U)
<< " ref=" << ref << " ref rb_state=" << ref->GetReadBarrierState()
<< " updated_all_immune_objects=" << updated_all_immune_objects;
}
} else { // Non-moving space and large-object space (LOS) cases. // If `ref` is on the allocation stack, then it may not be // marked live, but considered marked/alive (but not // necessarily on the live stack).
CHECK(IsMarkedInNonMovingSpace(ref))
<< "Unmarked ref that's not on the allocation stack."
<< " obj=" << obj
<< " ref=" << ref
<< " rb_state=" << ref->GetReadBarrierState()
<< " is_marking=" << std::boolalpha << is_marking_ << std::noboolalpha
<< " young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha
<< " done_scanning="
<< std::boolalpha << done_scanning_.load(std::memory_order_acquire) << std::noboolalpha
<< " self=" << Thread::Current();
}
}
// Used to scan ref fields of an object. template <bool kNoUnEvac> class ConcurrentCopying::RefFieldsVisitor { public: explicit RefFieldsVisitor(ConcurrentCopying* collector, Thread* const thread)
: collector_(collector), thread_(thread) { // Cannot have `kNoUnEvac` when Generational CC collection is disabled.
DCHECK_IMPLIES(kNoUnEvac, collector_->use_generational_cc_);
}
template <bool kNoUnEvac> inlinevoid ConcurrentCopying::Scan(mirror::Object* to_ref, size_t obj_size) { // Cannot have `kNoUnEvac` when Generational CC collection is disabled.
DCHECK_IMPLIES(kNoUnEvac, use_generational_cc_); if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) { // Avoid all read barriers during visit references to help performance. // Don't do this in transaction mode because we may read the old value of an field which may // trigger read barriers.
Thread::Current()->ModifyDebugDisallowReadBarrier(1);
} if (obj_size == 0) {
obj_size = to_ref->SizeOf<kDefaultVerifyFlags>();
}
bytes_scanned_ += obj_size;
DCHECK(!region_space_->IsInFromSpace(to_ref));
DCHECK_EQ(Thread::Current(), thread_running_gc_);
RefFieldsVisitor<kNoUnEvac> visitor(this, thread_running_gc_); // Disable the read barrier for a performance reason.
to_ref->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
visitor, visitor); if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) {
thread_running_gc_->ModifyDebugDisallowReadBarrier(-1);
}
}
template <bool kNoUnEvac> inlinevoid ConcurrentCopying::Process(mirror::Object* obj, MemberOffset offset) { // Cannot have `kNoUnEvac` when Generational CC collection is disabled.
DCHECK_IMPLIES(kNoUnEvac, use_generational_cc_);
DCHECK_EQ(Thread::Current(), thread_running_gc_);
mirror::Object* ref = obj->GetFieldObject<
mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset);
mirror::Object* to_ref = Mark</*kGrayImmuneObject=*/false, kNoUnEvac, /*kFromGCThread=*/true>(
thread_running_gc_,
ref, /*holder=*/ obj,
offset); if (to_ref == ref) { return;
} // This may fail if the mutator writes to the field at the same time. But it's ok.
mirror::Object* expected_ref = ref;
mirror::Object* new_ref = to_ref; do { if (expected_ref !=
obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset)) { // It was updated by the mutator. break;
} // Use release CAS to make sure threads reading the reference see contents of copied objects.
} while (!obj->CasFieldObjectWithoutWriteBarrier<false, false, kVerifyNone>(
offset,
expected_ref,
new_ref,
CASMode::kWeak,
std::memory_order_release));
}
// Process some roots. inlinevoid ConcurrentCopying::VisitRoots(mirror::Object*** roots,
size_t count,
[[maybe_unused]] const RootInfo& info) {
Thread* const self = Thread::Current(); for (size_t i = 0; i < count; ++i) {
mirror::Object** root = roots[i];
mirror::Object* ref = *root;
mirror::Object* to_ref = Mark(self, ref); if (to_ref == ref) { continue;
}
Atomic<mirror::Object*>* addr = reinterpret_cast<Atomic<mirror::Object*>*>(root);
mirror::Object* expected_ref = ref;
mirror::Object* new_ref = to_ref; do { if (expected_ref != addr->load(std::memory_order_relaxed)) { // It was updated by the mutator. break;
}
} while (!addr->CompareAndSetWeakRelaxed(expected_ref, new_ref));
}
}
template<bool kGrayImmuneObject> inlinevoid ConcurrentCopying::MarkRoot(Thread* const self,
mirror::CompressedReference<mirror::Object>* root) {
DCHECK(!root->IsNull());
mirror::Object* const ref = root->AsMirrorPtr();
mirror::Object* to_ref = Mark<kGrayImmuneObject>(self, ref); if (to_ref != ref) { auto* addr = reinterpret_cast<Atomic<mirror::CompressedReference<mirror::Object>>*>(root); auto expected_ref = mirror::CompressedReference<mirror::Object>::FromMirrorPtr(ref); auto new_ref = mirror::CompressedReference<mirror::Object>::FromMirrorPtr(to_ref); // If the cas fails, then it was updated by the mutator. do { if (ref != addr->load(std::memory_order_relaxed).AsMirrorPtr()) { // It was updated by the mutator. break;
}
} while (!addr->CompareAndSetWeakRelaxed(expected_ref, new_ref));
}
}
inlinevoid ConcurrentCopying::VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
size_t count,
[[maybe_unused]] const RootInfo& info) {
Thread* const self = Thread::Current(); for (size_t i = 0; i < count; ++i) {
mirror::CompressedReference<mirror::Object>* const root = roots[i]; if (!root->IsNull()) { // kGrayImmuneObject is true because this is used for the thread flip.
MarkRoot</*kGrayImmuneObject=*/true>(self, root);
}
}
}
// Temporary set gc_grays_immune_objects_ to true in a scope if the current thread is GC. class ConcurrentCopying::ScopedGcGraysImmuneObjects { public: explicit ScopedGcGraysImmuneObjects(ConcurrentCopying* collector)
: collector_(collector), enabled_(false) { if (kUseBakerReadBarrier &&
collector_->thread_running_gc_ == Thread::Current() &&
!collector_->gc_grays_immune_objects_) {
collector_->gc_grays_immune_objects_ = true;
enabled_ = true;
}
}
// Fill the given memory block with a fake object. Used to fill in a // copy of objects that was lost in race. void ConcurrentCopying::FillWithFakeObject(Thread* const self,
mirror::Object* fake_obj,
size_t byte_size) { // GC doesn't gray immune objects while scanning immune objects. But we need to trigger the read // barriers here because we need the updated reference to the int array class, etc. Temporary set // gc_grays_immune_objects_ to true so that we won't cause a DCHECK failure in MarkImmuneSpace().
ScopedGcGraysImmuneObjects scoped_gc_gray_immune_objects(this);
CHECK_ALIGNED(byte_size, kObjectAlignment);
memset(fake_obj, 0, byte_size); // Avoid going through read barrier for since kDisallowReadBarrierDuringScan may be enabled. // Explicitly mark to make sure to get an object in the to-space.
mirror::Class* int_array_class = down_cast<mirror::Class*>(
Mark(self, GetClassRoot<mirror::IntArray, kWithoutReadBarrier>().Ptr()));
CHECK(int_array_class != nullptr); if (ReadBarrier::kEnableToSpaceInvariantChecks) {
AssertToSpaceInvariant(nullptr, MemberOffset(0), int_array_class);
}
size_t component_size = int_array_class->GetComponentSize();
CHECK_EQ(component_size, sizeof(int32_t));
size_t data_offset = mirror::Array::DataOffset(component_size).SizeValue(); if (data_offset > byte_size) { // An int array is too big. Use java.lang.Object.
CHECK(java_lang_Object_ != nullptr); if (ReadBarrier::kEnableToSpaceInvariantChecks) {
AssertToSpaceInvariant(nullptr, MemberOffset(0), java_lang_Object_);
}
CHECK_EQ(byte_size, java_lang_Object_->GetObjectSize<kVerifyNone>());
fake_obj->SetClass(java_lang_Object_);
CHECK_EQ(byte_size, (fake_obj->SizeOf<kVerifyNone>()));
} else { // Use an int array.
fake_obj->SetClass(int_array_class);
CHECK(fake_obj->IsArrayInstance<kVerifyNone>());
int32_t length = (byte_size - data_offset) / component_size;
ObjPtr<mirror::Array> fake_arr = fake_obj->AsArray<kVerifyNone>();
fake_arr->SetLength(length);
CHECK_EQ(fake_arr->GetLength(), length)
<< "byte_size=" << byte_size << " length=" << length
<< " component_size=" << component_size << " data_offset=" << data_offset;
CHECK_EQ(byte_size, (fake_obj->SizeOf<kVerifyNone>()))
<< "byte_size=" << byte_size << " length=" << length
<< " component_size=" << component_size << " data_offset=" << data_offset;
}
}
// Reuse the memory blocks that were copy of objects that were lost in race.
mirror::Object* ConcurrentCopying::AllocateInSkippedBlock(Thread* const self, size_t alloc_size) { // Try to reuse the blocks that were unused due to CAS failures.
CHECK_ALIGNED(alloc_size, space::RegionSpace::kAlignment);
size_t min_object_size = RoundUp(sizeof(mirror::Object), space::RegionSpace::kAlignment);
size_t byte_size;
uint8_t* addr;
{
MutexLock mu(self, skipped_blocks_lock_); auto it = skipped_blocks_map_.lower_bound(alloc_size); if (it == skipped_blocks_map_.end()) { // Not found. return nullptr;
}
byte_size = it->first;
CHECK_GE(byte_size, alloc_size); if (byte_size > alloc_size && byte_size - alloc_size < min_object_size) { // If remainder would be too small for a fake object, retry with a larger request size.
it = skipped_blocks_map_.lower_bound(alloc_size + min_object_size); if (it == skipped_blocks_map_.end()) { // Not found. return nullptr;
}
CHECK_ALIGNED(it->first - alloc_size, space::RegionSpace::kAlignment);
CHECK_GE(it->first - alloc_size, min_object_size)
<< "byte_size=" << byte_size << " it->first=" << it->first << " alloc_size=" << alloc_size;
} // Found a block.
CHECK(it != skipped_blocks_map_.end());
byte_size = it->first;
addr = it->second;
CHECK_GE(byte_size, alloc_size);
CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr)));
CHECK_ALIGNED(byte_size, space::RegionSpace::kAlignment); if (kVerboseMode) {
LOG(INFO) << "Reusing skipped bytes : " << reinterpret_cast<void*>(addr) << ", " << byte_size;
}
skipped_blocks_map_.erase(it);
}
memset(addr, 0, byte_size); if (byte_size > alloc_size) { // Return the remainder to the map.
CHECK_ALIGNED(byte_size - alloc_size, space::RegionSpace::kAlignment);
CHECK_GE(byte_size - alloc_size, min_object_size); // FillWithFakeObject may mark an object, avoid holding skipped_blocks_lock_ to prevent lock // violation and possible deadlock. The deadlock case is a recursive case: // FillWithFakeObject -> Mark(IntArray.class) -> Copy -> AllocateInSkippedBlock.
FillWithFakeObject(self, reinterpret_cast<mirror::Object*>(addr + alloc_size),
byte_size - alloc_size);
CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr + alloc_size)));
{
MutexLock mu(self, skipped_blocks_lock_);
skipped_blocks_map_.insert(std::make_pair(byte_size - alloc_size, addr + alloc_size));
}
} returnreinterpret_cast<mirror::Object*>(addr);
}
mirror::Object* ConcurrentCopying::Copy(Thread* const self,
mirror::Object* from_ref,
mirror::Object* holder,
MemberOffset offset) {
DCHECK(region_space_->IsInFromSpace(from_ref)); // If the class pointer is null, the object is invalid. This could occur for a dangling pointer // from a previous GC that is either inside or outside the allocated region.
mirror::Class* klass = from_ref->GetClass<kVerifyNone, kWithoutReadBarrier>(); if (UNLIKELY(klass == nullptr)) { // Remove memory protection from the region space and log debugging information.
region_space_->Unprotect();
heap_->GetVerification()->LogHeapCorruption(holder, offset, from_ref, /* fatal= */ true);
} // There must not be a read barrier to avoid nested RB that might violate the to-space invariant. // Note that from_ref is a from space ref so the SizeOf() call will access the from-space meta // objects, but it's ok and necessary.
size_t obj_size = from_ref->SizeOf<kDefaultVerifyFlags>();
size_t region_space_alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment); // Large objects are never evacuated.
CHECK_LE(region_space_alloc_size, space::RegionSpace::kRegionSize);
size_t region_space_bytes_allocated = 0U;
size_t non_moving_space_bytes_allocated = 0U;
size_t bytes_allocated = 0U;
size_t unused_size; bool fall_back_to_non_moving = false;
mirror::Object* to_ref = region_space_->AllocNonvirtual</*kForEvac=*/ true>(
region_space_alloc_size, ®ion_space_bytes_allocated, nullptr, &unused_size);
bytes_allocated = region_space_bytes_allocated; if (LIKELY(to_ref != nullptr)) {
DCHECK_EQ(region_space_alloc_size, region_space_bytes_allocated);
} else { // Failed to allocate in the region space. Try the skipped blocks.
to_ref = AllocateInSkippedBlock(self, region_space_alloc_size); if (to_ref != nullptr) { // Succeeded to allocate in a skipped block. if (heap_->use_tlab_) { // This is necessary for the tlab case as it's not accounted in the space.
region_space_->RecordAlloc(to_ref);
}
bytes_allocated = region_space_alloc_size;
heap_->num_bytes_allocated_.fetch_sub(bytes_allocated, std::memory_order_relaxed);
to_space_bytes_skipped_.fetch_sub(bytes_allocated, std::memory_order_relaxed);
to_space_objects_skipped_.fetch_sub(1, std::memory_order_relaxed);
} else { // Fall back to the non-moving space.
fall_back_to_non_moving = true; if (kVerboseMode) {
LOG(INFO) << "Out of memory in the to-space. Fall back to non-moving. skipped_bytes="
<< to_space_bytes_skipped_.load(std::memory_order_relaxed)
<< " skipped_objects="
<< to_space_objects_skipped_.load(std::memory_order_relaxed);
}
to_ref = heap_->non_moving_space_->Alloc(
self, obj_size, &non_moving_space_bytes_allocated, nullptr, &unused_size); if (UNLIKELY(to_ref == nullptr)) {
LOG(FATAL_WITHOUT_ABORT) << "Fall-back non-moving space allocation failed for a "
<< obj_size << " byte object in region type "
<< region_space_->GetRegionType(from_ref);
LOG(FATAL) << "Object address=" << from_ref << " type=" << from_ref->PrettyTypeOf();
}
bytes_allocated = non_moving_space_bytes_allocated;
}
}
DCHECK(to_ref != nullptr);
// Copy the object excluding the lock word since that is handled in the loop.
to_ref->SetClass(klass); const size_t kObjectHeaderSize = sizeof(mirror::Object);
DCHECK_GE(obj_size, kObjectHeaderSize);
static_assert(kObjectHeaderSize == sizeof(mirror::HeapReference<mirror::Class>) + sizeof(LockWord), "Object header size does not match"); // Memcpy can tear for words since it may do byte copy. It is only safe to do this since the // object in the from space is immutable other than the lock word. b/31423258
memcpy(reinterpret_cast<uint8_t*>(to_ref) + kObjectHeaderSize, reinterpret_cast<const uint8_t*>(from_ref) + kObjectHeaderSize,
obj_size - kObjectHeaderSize);
// Attempt to install the forward pointer. This is in a loop as the // lock word atomic write can fail. while (true) {
LockWord old_lock_word = from_ref->GetLockWord(false);
if (old_lock_word.GetState() == LockWord::kForwardingAddress) { // Lost the race. Another thread (either GC or mutator) stored // the forwarding pointer first. Make the lost copy (to_ref) // look like a valid but dead (fake) object and keep it for // future reuse.
FillWithFakeObject(self, to_ref, bytes_allocated); if (!fall_back_to_non_moving) {
DCHECK(region_space_->IsInToSpace(to_ref)); // Record the lost copy for later reuse.
heap_->num_bytes_allocated_.fetch_add(bytes_allocated, std::memory_order_relaxed);
to_space_bytes_skipped_.fetch_add(bytes_allocated, std::memory_order_relaxed);
to_space_objects_skipped_.fetch_add(1, std::memory_order_relaxed);
MutexLock mu(self, skipped_blocks_lock_);
skipped_blocks_map_.insert(std::make_pair(bytes_allocated, reinterpret_cast<uint8_t*>(to_ref)));
} else {
DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated); // Free the non-moving-space chunk.
heap_->non_moving_space_->Free(self, to_ref);
}
// Copy the old lock word over since we did not copy it yet.
to_ref->SetLockWord(old_lock_word, false); // Set the gray ptr. if (kUseBakerReadBarrier) {
to_ref->SetReadBarrierState(ReadBarrier::GrayState());
}
// Try to atomically write the fwd ptr. Make sure that the copied object is visible to any // readers of the fwd pointer. bool success = from_ref->CasLockWord(old_lock_word,
new_lock_word,
CASMode::kWeak,
std::memory_order_release); if (LIKELY(success)) { // The CAS succeeded.
DCHECK(thread_running_gc_ != nullptr); if (LIKELY(self == thread_running_gc_)) {
objects_moved_gc_thread_ += 1;
bytes_moved_gc_thread_ += bytes_allocated;
} else {
objects_moved_.fetch_add(1, std::memory_order_relaxed);
bytes_moved_.fetch_add(bytes_allocated, std::memory_order_relaxed);
}
if (LIKELY(!fall_back_to_non_moving)) {
DCHECK(region_space_->IsInToSpace(to_ref));
} else {
DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated); if (!use_generational_cc_ || !young_gen_) { // Mark it in the live bitmap.
CHECK(!heap_->non_moving_space_->GetLiveBitmap()->AtomicTestAndSet(to_ref));
} if (!kUseBakerReadBarrier) { // Mark it in the mark bitmap.
CHECK(!heap_->non_moving_space_->GetMarkBitmap()->AtomicTestAndSet(to_ref));
}
} if (kUseBakerReadBarrier) {
DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState());
}
DCHECK(GetFwdPtr(from_ref) == to_ref);
CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress); // Make sure that anyone who sees to_ref also sees both the object contents and the // fwd pointer.
QuasiAtomic::ThreadFenceForConstructor();
PushOntoMarkStack(self, to_ref); return to_ref;
} else { // The CAS failed. It may have lost the race or may have failed // due to monitor/hashcode ops. Either way, retry.
}
}
}
mirror::Object* ConcurrentCopying::IsMarked(mirror::Object* from_ref) {
DCHECK(from_ref != nullptr);
space::RegionSpace::RegionType rtype = region_space_->GetRegionType(from_ref); if (rtype == space::RegionSpace::RegionType::kRegionTypeToSpace) { // It's already marked. return from_ref;
}
mirror::Object* to_ref; if (rtype == space::RegionSpace::RegionType::kRegionTypeFromSpace) {
to_ref = GetFwdPtr(from_ref);
DCHECK(to_ref == nullptr || region_space_->IsInToSpace(to_ref) ||
heap_->non_moving_space_->HasAddress(to_ref))
<< "from_ref=" << from_ref << " to_ref=" << to_ref;
} elseif (rtype == space::RegionSpace::RegionType::kRegionTypeUnevacFromSpace) { if (IsMarkedInUnevacFromSpace(from_ref)) {
to_ref = from_ref;
} else {
to_ref = nullptr;
}
} else { // At this point, `from_ref` should not be in the region space // (i.e. within an "unused" region).
DCHECK(!region_space_->HasAddress(from_ref)) << from_ref; // from_ref is in a non-moving space. if (immune_spaces_.ContainsObject(from_ref)) { // An immune object is alive.
to_ref = from_ref;
} else { // Non-immune non-moving space. Use the mark bitmap. if (IsMarkedInNonMovingSpace(from_ref)) { // Already marked.
to_ref = from_ref;
} else {
to_ref = nullptr;
}
}
} return to_ref;
}
bool ConcurrentCopying::IsOnAllocStack(mirror::Object* ref) { // Pairs with release fence after allocation-stack push in // Heap::AllocObjectWithAllocator().
std::atomic_thread_fence(std::memory_order_acquire);
accounting::ObjectStack* alloc_stack = GetAllocationStack(); return alloc_stack->Contains(ref);
}
mirror::Object* ConcurrentCopying::MarkNonMoving(Thread* const self,
mirror::Object* ref,
mirror::Object* holder,
MemberOffset offset) { // ref is in a non-moving space (from_ref == to_ref).
DCHECK(!region_space_->HasAddress(ref)) << ref;
DCHECK(!immune_spaces_.ContainsObject(ref)); // Use the mark bitmap.
accounting::ContinuousSpaceBitmap* mark_bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
accounting::LargeObjectBitmap* los_bitmap = nullptr; constbool is_los = !mark_bitmap->HasAddress(ref); if (is_los) {
VerifyLargeObject(ref, holder, offset);
los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
DCHECK(los_bitmap->HasAddress(ref));
} if (use_generational_cc_) { // The sticky-bit CC collector is only compatible with Baker-style read barriers.
DCHECK(kUseBakerReadBarrier); // Not done scanning, use AtomicSetReadBarrierPointer. if (!done_scanning_.load(std::memory_order_acquire)) { // Since the mark bitmap is still filled in from last GC, we can not use that or else the // mutator may see references to the from space. Instead, use the Baker pointer itself as // the mark bit. // // We need to avoid marking objects that are on allocation stack as that will lead to a // situation (after this GC cycle is finished) where some object(s) are on both allocation // stack and live bitmap. This leads to visiting the same object(s) twice during a heapdump // (b/117426281). if (!IsOnAllocStack(ref) &&
ref->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(), ReadBarrier::GrayState())) { // TODO: We don't actually need to scan this object later, we just need to clear the gray // bit. // We don't need to mark newly allocated objects (those in allocation stack) as they can // only point to to-space objects. Also, they are considered live till the next GC cycle.
PushOntoMarkStack(self, ref);
} return ref;
}
} if (!is_los && mark_bitmap->Test(ref)) { // Already marked.
} elseif (is_los && los_bitmap->Test(ref)) { // Already marked in LOS.
} elseif (IsOnAllocStack(ref)) { // If it's on the allocation stack, it's considered marked. Keep it white (non-gray). // Objects on the allocation stack need not be marked. if (!is_los) {
DCHECK(!mark_bitmap->Test(ref));
} else {
DCHECK(!los_bitmap->Test(ref));
} if (kUseBakerReadBarrier) {
DCHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::NonGrayState());
}
} else { // Not marked nor on the allocation stack. Try to mark it. // This may or may not succeed, which is ok. bool success = false; if (kUseBakerReadBarrier) {
success = ref->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(),
ReadBarrier::GrayState());
} else {
success = is_los ?
!los_bitmap->AtomicTestAndSet(ref) :
!mark_bitmap->AtomicTestAndSet(ref);
} if (success) { if (kUseBakerReadBarrier) {
DCHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::GrayState());
}
PushOntoMarkStack(self, ref);
}
} return ref;
}
void ConcurrentCopying::FinishPhase() {
Thread* const self = Thread::Current();
{
MutexLock mu(self, mark_stack_lock_);
CHECK(revoked_mark_stacks_.empty());
CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
} bool should_eagerly_release_memory = ShouldEagerlyReleaseMemoryToOS(); // kVerifyNoMissingCardMarks relies on the region space cards not being cleared to avoid false // positives. if (!kVerifyNoMissingCardMarks && !use_generational_cc_) {
TimingLogger::ScopedTiming split("ClearRegionSpaceCards", GetTimings()); // We do not currently use the region space cards at all, madvise them away to save ram.
heap_->GetCardTable()->ClearCardRange(region_space_->Begin(), region_space_->Limit());
} elseif (use_generational_cc_ && !young_gen_) {
region_space_inter_region_bitmap_.Clear(should_eagerly_release_memory);
non_moving_space_inter_region_bitmap_.Clear(should_eagerly_release_memory);
}
{
MutexLock mu(self, skipped_blocks_lock_);
skipped_blocks_map_.clear();
}
{
ReaderMutexLock mu(self, *Locks::mutator_lock_);
{
WriterMutexLock mu2(self, *Locks::heap_bitmap_lock_);
heap_->ClearMarkedObjects(should_eagerly_release_memory);
} if (kUseBakerReadBarrier && kFilterModUnionCards) {
TimingLogger::ScopedTiming split("FilterModUnionCards", GetTimings());
ReaderMutexLock mu2(self, *Locks::heap_bitmap_lock_); for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); // Filter out cards that don't need to be set. if (table != nullptr) {
table->FilterCards();
}
}
} if (kUseBakerReadBarrier) {
TimingLogger::ScopedTiming split("EmptyRBMarkBitStack", GetTimings());
DCHECK(rb_mark_bit_stack_ != nullptr); constauto* limit = rb_mark_bit_stack_->End(); for (StackReference<mirror::Object>* it = rb_mark_bit_stack_->Begin(); it != limit; ++it) {
CHECK(it->AsMirrorPtr()->AtomicSetMarkBit(1, 0))
<< "rb_mark_bit_stack_->Begin()" << rb_mark_bit_stack_->Begin() << '\n'
<< "rb_mark_bit_stack_->End()" << rb_mark_bit_stack_->End() << '\n'
<< "rb_mark_bit_stack_->IsFull()"
<< std::boolalpha << rb_mark_bit_stack_->IsFull() << std::noboolalpha << '\n'
<< DumpReferenceInfo(it->AsMirrorPtr(), "*it");
}
rb_mark_bit_stack_->Reset();
}
} if (measure_read_barrier_slow_path_) {
MutexLock mu(self, rb_slow_path_histogram_lock_);
rb_slow_path_time_histogram_.AdjustAndAddValue(
rb_slow_path_ns_.load(std::memory_order_relaxed));
rb_slow_path_count_total_ += rb_slow_path_count_.load(std::memory_order_relaxed);
rb_slow_path_count_gc_total_ += rb_slow_path_count_gc_.load(std::memory_order_relaxed);
}
}
bool ConcurrentCopying::IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object>* field) {
mirror::Object* from_ref = field->AsMirrorPtr(); if (from_ref == nullptr) { returntrue;
}
mirror::Object* to_ref = IsMarked(from_ref); if (to_ref == nullptr) { returnfalse;
} if (from_ref != to_ref) { // We have to update it while it may be concurrently overwritten by the mutator. // If the mutator overwrites it, we're done. while (UNLIKELY(!field->CasWeakRelaxed(from_ref, to_ref))) { if (field->AsMirrorPtr() != from_ref) { // Concurrently overwritten by a mutator. break;
}
} // See comment in MarkHeapReference() for memory ordering.
} returntrue;
}
void ConcurrentCopying::ProcessReferences(Thread* self) { // We don't really need to lock the heap bitmap lock as we use CAS to mark in bitmaps.
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
GetHeap()->GetReferenceProcessor()->ProcessReferences(self, GetTimings());
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
