1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "concurrent_copying.h" 18 19 #include "art_field-inl.h" 20 #include "base/enums.h" 21 #include "base/histogram-inl.h" 22 #include "base/stl_util.h" 23 #include "base/systrace.h" 24 #include "debugger.h" 25 #include "gc/accounting/atomic_stack.h" 26 #include "gc/accounting/heap_bitmap-inl.h" 27 #include "gc/accounting/mod_union_table-inl.h" 28 #include "gc/accounting/read_barrier_table.h" 29 #include "gc/accounting/space_bitmap-inl.h" 30 #include "gc/gc_pause_listener.h" 31 #include "gc/reference_processor.h" 32 #include "gc/space/image_space.h" 33 #include "gc/space/space-inl.h" 34 #include "gc/verification.h" 35 #include "image-inl.h" 36 #include "intern_table.h" 37 #include "mirror/class-inl.h" 38 #include "mirror/object-inl.h" 39 #include "mirror/object-refvisitor-inl.h" 40 #include "scoped_thread_state_change-inl.h" 41 #include "thread-inl.h" 42 #include "thread_list.h" 43 #include "well_known_classes.h" 44 45 namespace art { 46 namespace gc { 47 namespace collector { 48 49 static constexpr size_t kDefaultGcMarkStackSize = 2 * MB; 50 // If kFilterModUnionCards then we attempt to filter cards that don't need to be dirty in the mod 51 // union table. Disabled since it does not seem to help the pause much. 52 static constexpr bool kFilterModUnionCards = kIsDebugBuild; 53 // If kDisallowReadBarrierDuringScan is true then the GC aborts if there are any that occur during 54 // ConcurrentCopying::Scan. May be used to diagnose possibly unnecessary read barriers. 55 // Only enabled for kIsDebugBuild to avoid performance hit. 56 static constexpr bool kDisallowReadBarrierDuringScan = kIsDebugBuild; 57 // Slow path mark stack size, increase this if the stack is getting full and it is causing 58 // performance problems. 59 static constexpr size_t kReadBarrierMarkStackSize = 512 * KB; 60 // Verify that there are no missing card marks. 61 static constexpr bool kVerifyNoMissingCardMarks = kIsDebugBuild; 62 63 ConcurrentCopying::ConcurrentCopying(Heap* heap, 64 const std::string& name_prefix, 65 bool measure_read_barrier_slow_path) 66 : GarbageCollector(heap, 67 name_prefix + (name_prefix.empty() ? "" : " ") + 68 "concurrent copying"), 69 region_space_(nullptr), gc_barrier_(new Barrier(0)), 70 gc_mark_stack_(accounting::ObjectStack::Create("concurrent copying gc mark stack", 71 kDefaultGcMarkStackSize, 72 kDefaultGcMarkStackSize)), 73 rb_mark_bit_stack_(accounting::ObjectStack::Create("rb copying gc mark stack", 74 kReadBarrierMarkStackSize, 75 kReadBarrierMarkStackSize)), 76 rb_mark_bit_stack_full_(false), 77 mark_stack_lock_("concurrent copying mark stack lock", kMarkSweepMarkStackLock), 78 thread_running_gc_(nullptr), 79 is_marking_(false), 80 is_using_read_barrier_entrypoints_(false), 81 is_active_(false), 82 is_asserting_to_space_invariant_(false), 83 region_space_bitmap_(nullptr), 84 heap_mark_bitmap_(nullptr), 85 live_stack_freeze_size_(0), 86 from_space_num_objects_at_first_pause_(0), 87 from_space_num_bytes_at_first_pause_(0), 88 mark_stack_mode_(kMarkStackModeOff), 89 weak_ref_access_enabled_(true), 90 skipped_blocks_lock_("concurrent copying bytes blocks lock", kMarkSweepMarkStackLock), 91 measure_read_barrier_slow_path_(measure_read_barrier_slow_path), 92 mark_from_read_barrier_measurements_(false), 93 rb_slow_path_ns_(0), 94 rb_slow_path_count_(0), 95 rb_slow_path_count_gc_(0), 96 rb_slow_path_histogram_lock_("Read barrier histogram lock"), 97 rb_slow_path_time_histogram_("Mutator time in read barrier slow path", 500, 32), 98 rb_slow_path_count_total_(0), 99 rb_slow_path_count_gc_total_(0), 100 rb_table_(heap_->GetReadBarrierTable()), 101 force_evacuate_all_(false), 102 gc_grays_immune_objects_(false), 103 immune_gray_stack_lock_("concurrent copying immune gray stack lock", 104 kMarkSweepMarkStackLock) { 105 static_assert(space::RegionSpace::kRegionSize == accounting::ReadBarrierTable::kRegionSize, 106 "The region space size and the read barrier table region size must match"); 107 Thread* self = Thread::Current(); 108 { 109 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 110 // Cache this so that we won't have to lock heap_bitmap_lock_ in 111 // Mark() which could cause a nested lock on heap_bitmap_lock_ 112 // when GC causes a RB while doing GC or a lock order violation 113 // (class_linker_lock_ and heap_bitmap_lock_). 114 heap_mark_bitmap_ = heap->GetMarkBitmap(); 115 } 116 { 117 MutexLock mu(self, mark_stack_lock_); 118 for (size_t i = 0; i < kMarkStackPoolSize; ++i) { 119 accounting::AtomicStack<mirror::Object>* mark_stack = 120 accounting::AtomicStack<mirror::Object>::Create( 121 "thread local mark stack", kMarkStackSize, kMarkStackSize); 122 pooled_mark_stacks_.push_back(mark_stack); 123 } 124 } 125 } 126 127 void ConcurrentCopying::MarkHeapReference(mirror::HeapReference<mirror::Object>* field, 128 bool do_atomic_update) { 129 if (UNLIKELY(do_atomic_update)) { 130 // Used to mark the referent in DelayReferenceReferent in transaction mode. 131 mirror::Object* from_ref = field->AsMirrorPtr(); 132 if (from_ref == nullptr) { 133 return; 134 } 135 mirror::Object* to_ref = Mark(from_ref); 136 if (from_ref != to_ref) { 137 do { 138 if (field->AsMirrorPtr() != from_ref) { 139 // Concurrently overwritten by a mutator. 140 break; 141 } 142 } while (!field->CasWeakRelaxed(from_ref, to_ref)); 143 } 144 } else { 145 // Used for preserving soft references, should be OK to not have a CAS here since there should be 146 // no other threads which can trigger read barriers on the same referent during reference 147 // processing. 148 field->Assign(Mark(field->AsMirrorPtr())); 149 } 150 } 151 152 ConcurrentCopying::~ConcurrentCopying() { 153 STLDeleteElements(&pooled_mark_stacks_); 154 } 155 156 void ConcurrentCopying::RunPhases() { 157 CHECK(kUseBakerReadBarrier || kUseTableLookupReadBarrier); 158 CHECK(!is_active_); 159 is_active_ = true; 160 Thread* self = Thread::Current(); 161 thread_running_gc_ = self; 162 Locks::mutator_lock_->AssertNotHeld(self); 163 { 164 ReaderMutexLock mu(self, *Locks::mutator_lock_); 165 InitializePhase(); 166 } 167 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) { 168 // Switch to read barrier mark entrypoints before we gray the objects. This is required in case 169 // a mutator sees a gray bit and dispatches on the entrypoint. (b/37876887). 170 ActivateReadBarrierEntrypoints(); 171 // Gray dirty immune objects concurrently to reduce GC pause times. We re-process gray cards in 172 // the pause. 173 ReaderMutexLock mu(self, *Locks::mutator_lock_); 174 GrayAllDirtyImmuneObjects(); 175 } 176 FlipThreadRoots(); 177 { 178 ReaderMutexLock mu(self, *Locks::mutator_lock_); 179 MarkingPhase(); 180 } 181 // Verify no from space refs. This causes a pause. 182 if (kEnableNoFromSpaceRefsVerification) { 183 TimingLogger::ScopedTiming split("(Paused)VerifyNoFromSpaceReferences", GetTimings()); 184 ScopedPause pause(this, false); 185 CheckEmptyMarkStack(); 186 if (kVerboseMode) { 187 LOG(INFO) << "Verifying no from-space refs"; 188 } 189 VerifyNoFromSpaceReferences(); 190 if (kVerboseMode) { 191 LOG(INFO) << "Done verifying no from-space refs"; 192 } 193 CheckEmptyMarkStack(); 194 } 195 { 196 ReaderMutexLock mu(self, *Locks::mutator_lock_); 197 ReclaimPhase(); 198 } 199 FinishPhase(); 200 CHECK(is_active_); 201 is_active_ = false; 202 thread_running_gc_ = nullptr; 203 } 204 205 class ConcurrentCopying::ActivateReadBarrierEntrypointsCheckpoint : public Closure { 206 public: 207 explicit ActivateReadBarrierEntrypointsCheckpoint(ConcurrentCopying* concurrent_copying) 208 : concurrent_copying_(concurrent_copying) {} 209 210 void Run(Thread* thread) OVERRIDE NO_THREAD_SAFETY_ANALYSIS { 211 // Note: self is not necessarily equal to thread since thread may be suspended. 212 Thread* self = Thread::Current(); 213 DCHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 214 << thread->GetState() << " thread " << thread << " self " << self; 215 // Switch to the read barrier entrypoints. 216 thread->SetReadBarrierEntrypoints(); 217 // If thread is a running mutator, then act on behalf of the garbage collector. 218 // See the code in ThreadList::RunCheckpoint. 219 concurrent_copying_->GetBarrier().Pass(self); 220 } 221 222 private: 223 ConcurrentCopying* const concurrent_copying_; 224 }; 225 226 class ConcurrentCopying::ActivateReadBarrierEntrypointsCallback : public Closure { 227 public: 228 explicit ActivateReadBarrierEntrypointsCallback(ConcurrentCopying* concurrent_copying) 229 : concurrent_copying_(concurrent_copying) {} 230 231 void Run(Thread* self ATTRIBUTE_UNUSED) OVERRIDE REQUIRES(Locks::thread_list_lock_) { 232 // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint() 233 // to avoid a race with ThreadList::Register(). 234 CHECK(!concurrent_copying_->is_using_read_barrier_entrypoints_); 235 concurrent_copying_->is_using_read_barrier_entrypoints_ = true; 236 } 237 238 private: 239 ConcurrentCopying* const concurrent_copying_; 240 }; 241 242 void ConcurrentCopying::ActivateReadBarrierEntrypoints() { 243 Thread* const self = Thread::Current(); 244 ActivateReadBarrierEntrypointsCheckpoint checkpoint(this); 245 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 246 gc_barrier_->Init(self, 0); 247 ActivateReadBarrierEntrypointsCallback callback(this); 248 const size_t barrier_count = thread_list->RunCheckpoint(&checkpoint, &callback); 249 // If there are no threads to wait which implies that all the checkpoint functions are finished, 250 // then no need to release the mutator lock. 251 if (barrier_count == 0) { 252 return; 253 } 254 ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun); 255 gc_barrier_->Increment(self, barrier_count); 256 } 257 258 void ConcurrentCopying::BindBitmaps() { 259 Thread* self = Thread::Current(); 260 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 261 // Mark all of the spaces we never collect as immune. 262 for (const auto& space : heap_->GetContinuousSpaces()) { 263 if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect || 264 space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) { 265 CHECK(space->IsZygoteSpace() || space->IsImageSpace()); 266 immune_spaces_.AddSpace(space); 267 } else if (space == region_space_) { 268 // It is OK to clear the bitmap with mutators running since the only place it is read is 269 // VisitObjects which has exclusion with CC. 270 region_space_bitmap_ = region_space_->GetMarkBitmap(); 271 region_space_bitmap_->Clear(); 272 } 273 } 274 } 275 276 void ConcurrentCopying::InitializePhase() { 277 TimingLogger::ScopedTiming split("InitializePhase", GetTimings()); 278 if (kVerboseMode) { 279 LOG(INFO) << "GC InitializePhase"; 280 LOG(INFO) << "Region-space : " << reinterpret_cast<void*>(region_space_->Begin()) << "-" 281 << reinterpret_cast<void*>(region_space_->Limit()); 282 } 283 CheckEmptyMarkStack(); 284 if (kIsDebugBuild) { 285 MutexLock mu(Thread::Current(), mark_stack_lock_); 286 CHECK(false_gray_stack_.empty()); 287 } 288 289 rb_mark_bit_stack_full_ = false; 290 mark_from_read_barrier_measurements_ = measure_read_barrier_slow_path_; 291 if (measure_read_barrier_slow_path_) { 292 rb_slow_path_ns_.StoreRelaxed(0); 293 rb_slow_path_count_.StoreRelaxed(0); 294 rb_slow_path_count_gc_.StoreRelaxed(0); 295 } 296 297 immune_spaces_.Reset(); 298 bytes_moved_.StoreRelaxed(0); 299 objects_moved_.StoreRelaxed(0); 300 GcCause gc_cause = GetCurrentIteration()->GetGcCause(); 301 if (gc_cause == kGcCauseExplicit || 302 gc_cause == kGcCauseForNativeAllocBlocking || 303 gc_cause == kGcCauseCollectorTransition || 304 GetCurrentIteration()->GetClearSoftReferences()) { 305 force_evacuate_all_ = true; 306 } else { 307 force_evacuate_all_ = false; 308 } 309 if (kUseBakerReadBarrier) { 310 updated_all_immune_objects_.StoreRelaxed(false); 311 // GC may gray immune objects in the thread flip. 312 gc_grays_immune_objects_ = true; 313 if (kIsDebugBuild) { 314 MutexLock mu(Thread::Current(), immune_gray_stack_lock_); 315 DCHECK(immune_gray_stack_.empty()); 316 } 317 } 318 BindBitmaps(); 319 if (kVerboseMode) { 320 LOG(INFO) << "force_evacuate_all=" << force_evacuate_all_; 321 LOG(INFO) << "Largest immune region: " << immune_spaces_.GetLargestImmuneRegion().Begin() 322 << "-" << immune_spaces_.GetLargestImmuneRegion().End(); 323 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) { 324 LOG(INFO) << "Immune space: " << *space; 325 } 326 LOG(INFO) << "GC end of InitializePhase"; 327 } 328 // Mark all of the zygote large objects without graying them. 329 MarkZygoteLargeObjects(); 330 } 331 332 // Used to switch the thread roots of a thread from from-space refs to to-space refs. 333 class ConcurrentCopying::ThreadFlipVisitor : public Closure, public RootVisitor { 334 public: 335 ThreadFlipVisitor(ConcurrentCopying* concurrent_copying, bool use_tlab) 336 : concurrent_copying_(concurrent_copying), use_tlab_(use_tlab) { 337 } 338 339 virtual void Run(Thread* thread) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) { 340 // Note: self is not necessarily equal to thread since thread may be suspended. 341 Thread* self = Thread::Current(); 342 CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 343 << thread->GetState() << " thread " << thread << " self " << self; 344 thread->SetIsGcMarkingAndUpdateEntrypoints(true); 345 if (use_tlab_ && thread->HasTlab()) { 346 if (ConcurrentCopying::kEnableFromSpaceAccountingCheck) { 347 // This must come before the revoke. 348 size_t thread_local_objects = thread->GetThreadLocalObjectsAllocated(); 349 concurrent_copying_->region_space_->RevokeThreadLocalBuffers(thread); 350 reinterpret_cast<Atomic<size_t>*>(&concurrent_copying_->from_space_num_objects_at_first_pause_)-> 351 FetchAndAddSequentiallyConsistent(thread_local_objects); 352 } else { 353 concurrent_copying_->region_space_->RevokeThreadLocalBuffers(thread); 354 } 355 } 356 if (kUseThreadLocalAllocationStack) { 357 thread->RevokeThreadLocalAllocationStack(); 358 } 359 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 360 // We can use the non-CAS VisitRoots functions below because we update thread-local GC roots 361 // only. 362 thread->VisitRoots(this, kVisitRootFlagAllRoots); 363 concurrent_copying_->GetBarrier().Pass(self); 364 } 365 366 void VisitRoots(mirror::Object*** roots, 367 size_t count, 368 const RootInfo& info ATTRIBUTE_UNUSED) 369 REQUIRES_SHARED(Locks::mutator_lock_) { 370 for (size_t i = 0; i < count; ++i) { 371 mirror::Object** root = roots[i]; 372 mirror::Object* ref = *root; 373 if (ref != nullptr) { 374 mirror::Object* to_ref = concurrent_copying_->Mark(ref); 375 if (to_ref != ref) { 376 *root = to_ref; 377 } 378 } 379 } 380 } 381 382 void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, 383 size_t count, 384 const RootInfo& info ATTRIBUTE_UNUSED) 385 REQUIRES_SHARED(Locks::mutator_lock_) { 386 for (size_t i = 0; i < count; ++i) { 387 mirror::CompressedReference<mirror::Object>* const root = roots[i]; 388 if (!root->IsNull()) { 389 mirror::Object* ref = root->AsMirrorPtr(); 390 mirror::Object* to_ref = concurrent_copying_->Mark(ref); 391 if (to_ref != ref) { 392 root->Assign(to_ref); 393 } 394 } 395 } 396 } 397 398 private: 399 ConcurrentCopying* const concurrent_copying_; 400 const bool use_tlab_; 401 }; 402 403 // Called back from Runtime::FlipThreadRoots() during a pause. 404 class ConcurrentCopying::FlipCallback : public Closure { 405 public: 406 explicit FlipCallback(ConcurrentCopying* concurrent_copying) 407 : concurrent_copying_(concurrent_copying) { 408 } 409 410 virtual void Run(Thread* thread) OVERRIDE REQUIRES(Locks::mutator_lock_) { 411 ConcurrentCopying* cc = concurrent_copying_; 412 TimingLogger::ScopedTiming split("(Paused)FlipCallback", cc->GetTimings()); 413 // Note: self is not necessarily equal to thread since thread may be suspended. 414 Thread* self = Thread::Current(); 415 if (kVerifyNoMissingCardMarks) { 416 cc->VerifyNoMissingCardMarks(); 417 } 418 CHECK_EQ(thread, self); 419 Locks::mutator_lock_->AssertExclusiveHeld(self); 420 { 421 TimingLogger::ScopedTiming split2("(Paused)SetFromSpace", cc->GetTimings()); 422 cc->region_space_->SetFromSpace(cc->rb_table_, cc->force_evacuate_all_); 423 } 424 cc->SwapStacks(); 425 if (ConcurrentCopying::kEnableFromSpaceAccountingCheck) { 426 cc->RecordLiveStackFreezeSize(self); 427 cc->from_space_num_objects_at_first_pause_ = cc->region_space_->GetObjectsAllocated(); 428 cc->from_space_num_bytes_at_first_pause_ = cc->region_space_->GetBytesAllocated(); 429 } 430 cc->is_marking_ = true; 431 cc->mark_stack_mode_.StoreRelaxed(ConcurrentCopying::kMarkStackModeThreadLocal); 432 if (kIsDebugBuild) { 433 cc->region_space_->AssertAllRegionLiveBytesZeroOrCleared(); 434 } 435 if (UNLIKELY(Runtime::Current()->IsActiveTransaction())) { 436 CHECK(Runtime::Current()->IsAotCompiler()); 437 TimingLogger::ScopedTiming split3("(Paused)VisitTransactionRoots", cc->GetTimings()); 438 Runtime::Current()->VisitTransactionRoots(cc); 439 } 440 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) { 441 cc->GrayAllNewlyDirtyImmuneObjects(); 442 if (kIsDebugBuild) { 443 // Check that all non-gray immune objects only refernce immune objects. 444 cc->VerifyGrayImmuneObjects(); 445 } 446 } 447 // May be null during runtime creation, in this case leave java_lang_Object null. 448 // This is safe since single threaded behavior should mean FillDummyObject does not 449 // happen when java_lang_Object_ is null. 450 if (WellKnownClasses::java_lang_Object != nullptr) { 451 cc->java_lang_Object_ = down_cast<mirror::Class*>(cc->Mark( 452 WellKnownClasses::ToClass(WellKnownClasses::java_lang_Object).Ptr())); 453 } else { 454 cc->java_lang_Object_ = nullptr; 455 } 456 } 457 458 private: 459 ConcurrentCopying* const concurrent_copying_; 460 }; 461 462 class ConcurrentCopying::VerifyGrayImmuneObjectsVisitor { 463 public: 464 explicit VerifyGrayImmuneObjectsVisitor(ConcurrentCopying* collector) 465 : collector_(collector) {} 466 467 void operator()(ObjPtr<mirror::Object> obj, MemberOffset offset, bool /* is_static */) 468 const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_) 469 REQUIRES_SHARED(Locks::heap_bitmap_lock_) { 470 CheckReference(obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset), 471 obj, offset); 472 } 473 474 void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const 475 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 476 CHECK(klass->IsTypeOfReferenceClass()); 477 CheckReference(ref->GetReferent<kWithoutReadBarrier>(), 478 ref, 479 mirror::Reference::ReferentOffset()); 480 } 481 482 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 483 ALWAYS_INLINE 484 REQUIRES_SHARED(Locks::mutator_lock_) { 485 if (!root->IsNull()) { 486 VisitRoot(root); 487 } 488 } 489 490 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 491 ALWAYS_INLINE 492 REQUIRES_SHARED(Locks::mutator_lock_) { 493 CheckReference(root->AsMirrorPtr(), nullptr, MemberOffset(0)); 494 } 495 496 private: 497 ConcurrentCopying* const collector_; 498 499 void CheckReference(ObjPtr<mirror::Object> ref, 500 ObjPtr<mirror::Object> holder, 501 MemberOffset offset) const 502 REQUIRES_SHARED(Locks::mutator_lock_) { 503 if (ref != nullptr) { 504 if (!collector_->immune_spaces_.ContainsObject(ref.Ptr())) { 505 // Not immune, must be a zygote large object. 506 CHECK(Runtime::Current()->GetHeap()->GetLargeObjectsSpace()->IsZygoteLargeObject( 507 Thread::Current(), ref.Ptr())) 508 << "Non gray object references non immune, non zygote large object "<< ref << " " 509 << mirror::Object::PrettyTypeOf(ref) << " in holder " << holder << " " 510 << mirror::Object::PrettyTypeOf(holder) << " offset=" << offset.Uint32Value(); 511 } else { 512 // Make sure the large object class is immune since we will never scan the large object. 513 CHECK(collector_->immune_spaces_.ContainsObject( 514 ref->GetClass<kVerifyNone, kWithoutReadBarrier>())); 515 } 516 } 517 } 518 }; 519 520 void ConcurrentCopying::VerifyGrayImmuneObjects() { 521 TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings()); 522 for (auto& space : immune_spaces_.GetSpaces()) { 523 DCHECK(space->IsImageSpace() || space->IsZygoteSpace()); 524 accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap(); 525 VerifyGrayImmuneObjectsVisitor visitor(this); 526 live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()), 527 reinterpret_cast<uintptr_t>(space->Limit()), 528 [&visitor](mirror::Object* obj) 529 REQUIRES_SHARED(Locks::mutator_lock_) { 530 // If an object is not gray, it should only have references to things in the immune spaces. 531 if (obj->GetReadBarrierState() != ReadBarrier::GrayState()) { 532 obj->VisitReferences</*kVisitNativeRoots*/true, 533 kDefaultVerifyFlags, 534 kWithoutReadBarrier>(visitor, visitor); 535 } 536 }); 537 } 538 } 539 540 class ConcurrentCopying::VerifyNoMissingCardMarkVisitor { 541 public: 542 VerifyNoMissingCardMarkVisitor(ConcurrentCopying* cc, ObjPtr<mirror::Object> holder) 543 : cc_(cc), 544 holder_(holder) {} 545 546 void operator()(ObjPtr<mirror::Object> obj, 547 MemberOffset offset, 548 bool is_static ATTRIBUTE_UNUSED) const 549 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 550 if (offset.Uint32Value() != mirror::Object::ClassOffset().Uint32Value()) { 551 CheckReference(obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>( 552 offset), offset.Uint32Value()); 553 } 554 } 555 void operator()(ObjPtr<mirror::Class> klass, 556 ObjPtr<mirror::Reference> ref) const 557 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 558 CHECK(klass->IsTypeOfReferenceClass()); 559 this->operator()(ref, mirror::Reference::ReferentOffset(), false); 560 } 561 562 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 563 REQUIRES_SHARED(Locks::mutator_lock_) { 564 if (!root->IsNull()) { 565 VisitRoot(root); 566 } 567 } 568 569 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 570 REQUIRES_SHARED(Locks::mutator_lock_) { 571 CheckReference(root->AsMirrorPtr()); 572 } 573 574 void CheckReference(mirror::Object* ref, int32_t offset = -1) const 575 REQUIRES_SHARED(Locks::mutator_lock_) { 576 CHECK(ref == nullptr || !cc_->region_space_->IsInNewlyAllocatedRegion(ref)) 577 << holder_->PrettyTypeOf() << "(" << holder_.Ptr() << ") references object " 578 << ref->PrettyTypeOf() << "(" << ref << ") in newly allocated region at offset=" << offset; 579 } 580 581 private: 582 ConcurrentCopying* const cc_; 583 ObjPtr<mirror::Object> const holder_; 584 }; 585 586 void ConcurrentCopying::VerifyNoMissingCardMarks() { 587 auto visitor = [&](mirror::Object* obj) 588 REQUIRES(Locks::mutator_lock_) 589 REQUIRES(!mark_stack_lock_) { 590 // Objects not on dirty or aged cards should never have references to newly allocated regions. 591 if (heap_->GetCardTable()->GetCard(obj) == gc::accounting::CardTable::kCardClean) { 592 VerifyNoMissingCardMarkVisitor internal_visitor(this, /*holder*/ obj); 593 obj->VisitReferences</*kVisitNativeRoots*/true, kVerifyNone, kWithoutReadBarrier>( 594 internal_visitor, internal_visitor); 595 } 596 }; 597 TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings()); 598 region_space_->Walk(visitor); 599 { 600 ReaderMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_); 601 heap_->GetLiveBitmap()->Visit(visitor); 602 } 603 } 604 605 // Switch threads that from from-space to to-space refs. Forward/mark the thread roots. 606 void ConcurrentCopying::FlipThreadRoots() { 607 TimingLogger::ScopedTiming split("FlipThreadRoots", GetTimings()); 608 if (kVerboseMode) { 609 LOG(INFO) << "time=" << region_space_->Time(); 610 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO)); 611 } 612 Thread* self = Thread::Current(); 613 Locks::mutator_lock_->AssertNotHeld(self); 614 gc_barrier_->Init(self, 0); 615 ThreadFlipVisitor thread_flip_visitor(this, heap_->use_tlab_); 616 FlipCallback flip_callback(this); 617 618 size_t barrier_count = Runtime::Current()->GetThreadList()->FlipThreadRoots( 619 &thread_flip_visitor, &flip_callback, this, GetHeap()->GetGcPauseListener()); 620 621 { 622 ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun); 623 gc_barrier_->Increment(self, barrier_count); 624 } 625 is_asserting_to_space_invariant_ = true; 626 QuasiAtomic::ThreadFenceForConstructor(); 627 if (kVerboseMode) { 628 LOG(INFO) << "time=" << region_space_->Time(); 629 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO)); 630 LOG(INFO) << "GC end of FlipThreadRoots"; 631 } 632 } 633 634 template <bool kConcurrent> 635 class ConcurrentCopying::GrayImmuneObjectVisitor { 636 public: 637 explicit GrayImmuneObjectVisitor(Thread* self) : self_(self) {} 638 639 ALWAYS_INLINE void operator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) { 640 if (kUseBakerReadBarrier && obj->GetReadBarrierState() == ReadBarrier::WhiteState()) { 641 if (kConcurrent) { 642 Locks::mutator_lock_->AssertSharedHeld(self_); 643 obj->AtomicSetReadBarrierState(ReadBarrier::WhiteState(), ReadBarrier::GrayState()); 644 // Mod union table VisitObjects may visit the same object multiple times so we can't check 645 // the result of the atomic set. 646 } else { 647 Locks::mutator_lock_->AssertExclusiveHeld(self_); 648 obj->SetReadBarrierState(ReadBarrier::GrayState()); 649 } 650 } 651 } 652 653 static void Callback(mirror::Object* obj, void* arg) REQUIRES_SHARED(Locks::mutator_lock_) { 654 reinterpret_cast<GrayImmuneObjectVisitor<kConcurrent>*>(arg)->operator()(obj); 655 } 656 657 private: 658 Thread* const self_; 659 }; 660 661 void ConcurrentCopying::GrayAllDirtyImmuneObjects() { 662 TimingLogger::ScopedTiming split("GrayAllDirtyImmuneObjects", GetTimings()); 663 accounting::CardTable* const card_table = heap_->GetCardTable(); 664 Thread* const self = Thread::Current(); 665 using VisitorType = GrayImmuneObjectVisitor</* kIsConcurrent */ true>; 666 VisitorType visitor(self); 667 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 668 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) { 669 DCHECK(space->IsImageSpace() || space->IsZygoteSpace()); 670 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); 671 // Mark all the objects on dirty cards since these may point to objects in other space. 672 // Once these are marked, the GC will eventually clear them later. 673 // Table is non null for boot image and zygote spaces. It is only null for application image 674 // spaces. 675 if (table != nullptr) { 676 table->ProcessCards(); 677 table->VisitObjects(&VisitorType::Callback, &visitor); 678 // Don't clear cards here since we need to rescan in the pause. If we cleared the cards here, 679 // there would be races with the mutator marking new cards. 680 } else { 681 // Keep cards aged if we don't have a mod-union table since we may need to scan them in future 682 // GCs. This case is for app images. 683 card_table->ModifyCardsAtomic( 684 space->Begin(), 685 space->End(), 686 [](uint8_t card) { 687 return (card != gc::accounting::CardTable::kCardClean) 688 ? gc::accounting::CardTable::kCardAged 689 : card; 690 }, 691 /* card modified visitor */ VoidFunctor()); 692 card_table->Scan</* kClearCard */ false>(space->GetMarkBitmap(), 693 space->Begin(), 694 space->End(), 695 visitor, 696 gc::accounting::CardTable::kCardAged); 697 } 698 } 699 } 700 701 void ConcurrentCopying::GrayAllNewlyDirtyImmuneObjects() { 702 TimingLogger::ScopedTiming split("(Paused)GrayAllNewlyDirtyImmuneObjects", GetTimings()); 703 accounting::CardTable* const card_table = heap_->GetCardTable(); 704 using VisitorType = GrayImmuneObjectVisitor</* kIsConcurrent */ false>; 705 Thread* const self = Thread::Current(); 706 VisitorType visitor(self); 707 WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_); 708 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) { 709 DCHECK(space->IsImageSpace() || space->IsZygoteSpace()); 710 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); 711 712 // Don't need to scan aged cards since we did these before the pause. Note that scanning cards 713 // also handles the mod-union table cards. 714 card_table->Scan</* kClearCard */ false>(space->GetMarkBitmap(), 715 space->Begin(), 716 space->End(), 717 visitor, 718 gc::accounting::CardTable::kCardDirty); 719 if (table != nullptr) { 720 // Add the cards to the mod-union table so that we can clear cards to save RAM. 721 table->ProcessCards(); 722 TimingLogger::ScopedTiming split2("(Paused)ClearCards", GetTimings()); 723 card_table->ClearCardRange(space->Begin(), 724 AlignDown(space->End(), accounting::CardTable::kCardSize)); 725 } 726 } 727 // Since all of the objects that may point to other spaces are gray, we can avoid all the read 728 // barriers in the immune spaces. 729 updated_all_immune_objects_.StoreRelaxed(true); 730 } 731 732 void ConcurrentCopying::SwapStacks() { 733 heap_->SwapStacks(); 734 } 735 736 void ConcurrentCopying::RecordLiveStackFreezeSize(Thread* self) { 737 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 738 live_stack_freeze_size_ = heap_->GetLiveStack()->Size(); 739 } 740 741 // Used to visit objects in the immune spaces. 742 inline void ConcurrentCopying::ScanImmuneObject(mirror::Object* obj) { 743 DCHECK(obj != nullptr); 744 DCHECK(immune_spaces_.ContainsObject(obj)); 745 // Update the fields without graying it or pushing it onto the mark stack. 746 Scan(obj); 747 } 748 749 class ConcurrentCopying::ImmuneSpaceScanObjVisitor { 750 public: 751 explicit ImmuneSpaceScanObjVisitor(ConcurrentCopying* cc) 752 : collector_(cc) {} 753 754 ALWAYS_INLINE void operator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) { 755 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) { 756 // Only need to scan gray objects. 757 if (obj->GetReadBarrierState() == ReadBarrier::GrayState()) { 758 collector_->ScanImmuneObject(obj); 759 // Done scanning the object, go back to white. 760 bool success = obj->AtomicSetReadBarrierState(ReadBarrier::GrayState(), 761 ReadBarrier::WhiteState()); 762 CHECK(success); 763 } 764 } else { 765 collector_->ScanImmuneObject(obj); 766 } 767 } 768 769 static void Callback(mirror::Object* obj, void* arg) REQUIRES_SHARED(Locks::mutator_lock_) { 770 reinterpret_cast<ImmuneSpaceScanObjVisitor*>(arg)->operator()(obj); 771 } 772 773 private: 774 ConcurrentCopying* const collector_; 775 }; 776 777 // Concurrently mark roots that are guarded by read barriers and process the mark stack. 778 void ConcurrentCopying::MarkingPhase() { 779 TimingLogger::ScopedTiming split("MarkingPhase", GetTimings()); 780 if (kVerboseMode) { 781 LOG(INFO) << "GC MarkingPhase"; 782 } 783 Thread* self = Thread::Current(); 784 if (kIsDebugBuild) { 785 MutexLock mu(self, *Locks::thread_list_lock_); 786 CHECK(weak_ref_access_enabled_); 787 } 788 789 // Scan immune spaces. 790 // Update all the fields in the immune spaces first without graying the objects so that we 791 // minimize dirty pages in the immune spaces. Note mutators can concurrently access and gray some 792 // of the objects. 793 if (kUseBakerReadBarrier) { 794 gc_grays_immune_objects_ = false; 795 } 796 { 797 TimingLogger::ScopedTiming split2("ScanImmuneSpaces", GetTimings()); 798 for (auto& space : immune_spaces_.GetSpaces()) { 799 DCHECK(space->IsImageSpace() || space->IsZygoteSpace()); 800 accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap(); 801 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); 802 ImmuneSpaceScanObjVisitor visitor(this); 803 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects && table != nullptr) { 804 table->VisitObjects(ImmuneSpaceScanObjVisitor::Callback, &visitor); 805 } else { 806 // TODO: Scan only the aged cards. 807 live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()), 808 reinterpret_cast<uintptr_t>(space->Limit()), 809 visitor); 810 } 811 } 812 } 813 if (kUseBakerReadBarrier) { 814 // This release fence makes the field updates in the above loop visible before allowing mutator 815 // getting access to immune objects without graying it first. 816 updated_all_immune_objects_.StoreRelease(true); 817 // Now whiten immune objects concurrently accessed and grayed by mutators. We can't do this in 818 // the above loop because we would incorrectly disable the read barrier by whitening an object 819 // which may point to an unscanned, white object, breaking the to-space invariant. 820 // 821 // Make sure no mutators are in the middle of marking an immune object before whitening immune 822 // objects. 823 IssueEmptyCheckpoint(); 824 MutexLock mu(Thread::Current(), immune_gray_stack_lock_); 825 if (kVerboseMode) { 826 LOG(INFO) << "immune gray stack size=" << immune_gray_stack_.size(); 827 } 828 for (mirror::Object* obj : immune_gray_stack_) { 829 DCHECK(obj->GetReadBarrierState() == ReadBarrier::GrayState()); 830 bool success = obj->AtomicSetReadBarrierState(ReadBarrier::GrayState(), 831 ReadBarrier::WhiteState()); 832 DCHECK(success); 833 } 834 immune_gray_stack_.clear(); 835 } 836 837 { 838 TimingLogger::ScopedTiming split2("VisitConcurrentRoots", GetTimings()); 839 Runtime::Current()->VisitConcurrentRoots(this, kVisitRootFlagAllRoots); 840 } 841 { 842 // TODO: don't visit the transaction roots if it's not active. 843 TimingLogger::ScopedTiming split5("VisitNonThreadRoots", GetTimings()); 844 Runtime::Current()->VisitNonThreadRoots(this); 845 } 846 847 { 848 TimingLogger::ScopedTiming split7("ProcessMarkStack", GetTimings()); 849 // We transition through three mark stack modes (thread-local, shared, GC-exclusive). The 850 // primary reasons are the fact that we need to use a checkpoint to process thread-local mark 851 // stacks, but after we disable weak refs accesses, we can't use a checkpoint due to a deadlock 852 // issue because running threads potentially blocking at WaitHoldingLocks, and that once we 853 // reach the point where we process weak references, we can avoid using a lock when accessing 854 // the GC mark stack, which makes mark stack processing more efficient. 855 856 // Process the mark stack once in the thread local stack mode. This marks most of the live 857 // objects, aside from weak ref accesses with read barriers (Reference::GetReferent() and system 858 // weaks) that may happen concurrently while we processing the mark stack and newly mark/gray 859 // objects and push refs on the mark stack. 860 ProcessMarkStack(); 861 // Switch to the shared mark stack mode. That is, revoke and process thread-local mark stacks 862 // for the last time before transitioning to the shared mark stack mode, which would process new 863 // refs that may have been concurrently pushed onto the mark stack during the ProcessMarkStack() 864 // call above. At the same time, disable weak ref accesses using a per-thread flag. It's 865 // important to do these together in a single checkpoint so that we can ensure that mutators 866 // won't newly gray objects and push new refs onto the mark stack due to weak ref accesses and 867 // mutators safely transition to the shared mark stack mode (without leaving unprocessed refs on 868 // the thread-local mark stacks), without a race. This is why we use a thread-local weak ref 869 // access flag Thread::tls32_.weak_ref_access_enabled_ instead of the global ones. 870 SwitchToSharedMarkStackMode(); 871 CHECK(!self->GetWeakRefAccessEnabled()); 872 // Now that weak refs accesses are disabled, once we exhaust the shared mark stack again here 873 // (which may be non-empty if there were refs found on thread-local mark stacks during the above 874 // SwitchToSharedMarkStackMode() call), we won't have new refs to process, that is, mutators 875 // (via read barriers) have no way to produce any more refs to process. Marking converges once 876 // before we process weak refs below. 877 ProcessMarkStack(); 878 CheckEmptyMarkStack(); 879 // Switch to the GC exclusive mark stack mode so that we can process the mark stack without a 880 // lock from this point on. 881 SwitchToGcExclusiveMarkStackMode(); 882 CheckEmptyMarkStack(); 883 if (kVerboseMode) { 884 LOG(INFO) << "ProcessReferences"; 885 } 886 // Process weak references. This may produce new refs to process and have them processed via 887 // ProcessMarkStack (in the GC exclusive mark stack mode). 888 ProcessReferences(self); 889 CheckEmptyMarkStack(); 890 if (kVerboseMode) { 891 LOG(INFO) << "SweepSystemWeaks"; 892 } 893 SweepSystemWeaks(self); 894 if (kVerboseMode) { 895 LOG(INFO) << "SweepSystemWeaks done"; 896 } 897 // Process the mark stack here one last time because the above SweepSystemWeaks() call may have 898 // marked some objects (strings alive) as hash_set::Erase() can call the hash function for 899 // arbitrary elements in the weak intern table in InternTable::Table::SweepWeaks(). 900 ProcessMarkStack(); 901 CheckEmptyMarkStack(); 902 // Re-enable weak ref accesses. 903 ReenableWeakRefAccess(self); 904 // Free data for class loaders that we unloaded. 905 Runtime::Current()->GetClassLinker()->CleanupClassLoaders(); 906 // Marking is done. Disable marking. 907 DisableMarking(); 908 if (kUseBakerReadBarrier) { 909 ProcessFalseGrayStack(); 910 } 911 CheckEmptyMarkStack(); 912 } 913 914 if (kIsDebugBuild) { 915 MutexLock mu(self, *Locks::thread_list_lock_); 916 CHECK(weak_ref_access_enabled_); 917 } 918 if (kVerboseMode) { 919 LOG(INFO) << "GC end of MarkingPhase"; 920 } 921 } 922 923 void ConcurrentCopying::ReenableWeakRefAccess(Thread* self) { 924 if (kVerboseMode) { 925 LOG(INFO) << "ReenableWeakRefAccess"; 926 } 927 // Iterate all threads (don't need to or can't use a checkpoint) and re-enable weak ref access. 928 { 929 MutexLock mu(self, *Locks::thread_list_lock_); 930 weak_ref_access_enabled_ = true; // This is for new threads. 931 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 932 for (Thread* thread : thread_list) { 933 thread->SetWeakRefAccessEnabled(true); 934 } 935 } 936 // Unblock blocking threads. 937 GetHeap()->GetReferenceProcessor()->BroadcastForSlowPath(self); 938 Runtime::Current()->BroadcastForNewSystemWeaks(); 939 } 940 941 class ConcurrentCopying::DisableMarkingCheckpoint : public Closure { 942 public: 943 explicit DisableMarkingCheckpoint(ConcurrentCopying* concurrent_copying) 944 : concurrent_copying_(concurrent_copying) { 945 } 946 947 void Run(Thread* thread) OVERRIDE NO_THREAD_SAFETY_ANALYSIS { 948 // Note: self is not necessarily equal to thread since thread may be suspended. 949 Thread* self = Thread::Current(); 950 DCHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 951 << thread->GetState() << " thread " << thread << " self " << self; 952 // Disable the thread-local is_gc_marking flag. 953 // Note a thread that has just started right before this checkpoint may have already this flag 954 // set to false, which is ok. 955 thread->SetIsGcMarkingAndUpdateEntrypoints(false); 956 // If thread is a running mutator, then act on behalf of the garbage collector. 957 // See the code in ThreadList::RunCheckpoint. 958 concurrent_copying_->GetBarrier().Pass(self); 959 } 960 961 private: 962 ConcurrentCopying* const concurrent_copying_; 963 }; 964 965 class ConcurrentCopying::DisableMarkingCallback : public Closure { 966 public: 967 explicit DisableMarkingCallback(ConcurrentCopying* concurrent_copying) 968 : concurrent_copying_(concurrent_copying) { 969 } 970 971 void Run(Thread* self ATTRIBUTE_UNUSED) OVERRIDE REQUIRES(Locks::thread_list_lock_) { 972 // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint() 973 // to avoid a race with ThreadList::Register(). 974 CHECK(concurrent_copying_->is_marking_); 975 concurrent_copying_->is_marking_ = false; 976 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) { 977 CHECK(concurrent_copying_->is_using_read_barrier_entrypoints_); 978 concurrent_copying_->is_using_read_barrier_entrypoints_ = false; 979 } else { 980 CHECK(!concurrent_copying_->is_using_read_barrier_entrypoints_); 981 } 982 } 983 984 private: 985 ConcurrentCopying* const concurrent_copying_; 986 }; 987 988 void ConcurrentCopying::IssueDisableMarkingCheckpoint() { 989 Thread* self = Thread::Current(); 990 DisableMarkingCheckpoint check_point(this); 991 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 992 gc_barrier_->Init(self, 0); 993 DisableMarkingCallback dmc(this); 994 size_t barrier_count = thread_list->RunCheckpoint(&check_point, &dmc); 995 // If there are no threads to wait which implies that all the checkpoint functions are finished, 996 // then no need to release the mutator lock. 997 if (barrier_count == 0) { 998 return; 999 } 1000 // Release locks then wait for all mutator threads to pass the barrier. 1001 Locks::mutator_lock_->SharedUnlock(self); 1002 { 1003 ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun); 1004 gc_barrier_->Increment(self, barrier_count); 1005 } 1006 Locks::mutator_lock_->SharedLock(self); 1007 } 1008 1009 void ConcurrentCopying::DisableMarking() { 1010 // Use a checkpoint to turn off the global is_marking and the thread-local is_gc_marking flags and 1011 // to ensure no threads are still in the middle of a read barrier which may have a from-space ref 1012 // cached in a local variable. 1013 IssueDisableMarkingCheckpoint(); 1014 if (kUseTableLookupReadBarrier) { 1015 heap_->rb_table_->ClearAll(); 1016 DCHECK(heap_->rb_table_->IsAllCleared()); 1017 } 1018 is_mark_stack_push_disallowed_.StoreSequentiallyConsistent(1); 1019 mark_stack_mode_.StoreSequentiallyConsistent(kMarkStackModeOff); 1020 } 1021 1022 void ConcurrentCopying::PushOntoFalseGrayStack(mirror::Object* ref) { 1023 CHECK(kUseBakerReadBarrier); 1024 DCHECK(ref != nullptr); 1025 MutexLock mu(Thread::Current(), mark_stack_lock_); 1026 false_gray_stack_.push_back(ref); 1027 } 1028 1029 void ConcurrentCopying::ProcessFalseGrayStack() { 1030 CHECK(kUseBakerReadBarrier); 1031 // Change the objects on the false gray stack from gray to white. 1032 MutexLock mu(Thread::Current(), mark_stack_lock_); 1033 for (mirror::Object* obj : false_gray_stack_) { 1034 DCHECK(IsMarked(obj)); 1035 // The object could be white here if a thread got preempted after a success at the 1036 // AtomicSetReadBarrierState in Mark(), GC started marking through it (but not finished so 1037 // still gray), and the thread ran to register it onto the false gray stack. 1038 if (obj->GetReadBarrierState() == ReadBarrier::GrayState()) { 1039 bool success = obj->AtomicSetReadBarrierState(ReadBarrier::GrayState(), 1040 ReadBarrier::WhiteState()); 1041 DCHECK(success); 1042 } 1043 } 1044 false_gray_stack_.clear(); 1045 } 1046 1047 void ConcurrentCopying::IssueEmptyCheckpoint() { 1048 Thread* self = Thread::Current(); 1049 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 1050 // Release locks then wait for all mutator threads to pass the barrier. 1051 Locks::mutator_lock_->SharedUnlock(self); 1052 thread_list->RunEmptyCheckpoint(); 1053 Locks::mutator_lock_->SharedLock(self); 1054 } 1055 1056 void ConcurrentCopying::ExpandGcMarkStack() { 1057 DCHECK(gc_mark_stack_->IsFull()); 1058 const size_t new_size = gc_mark_stack_->Capacity() * 2; 1059 std::vector<StackReference<mirror::Object>> temp(gc_mark_stack_->Begin(), 1060 gc_mark_stack_->End()); 1061 gc_mark_stack_->Resize(new_size); 1062 for (auto& ref : temp) { 1063 gc_mark_stack_->PushBack(ref.AsMirrorPtr()); 1064 } 1065 DCHECK(!gc_mark_stack_->IsFull()); 1066 } 1067 1068 void ConcurrentCopying::PushOntoMarkStack(mirror::Object* to_ref) { 1069 CHECK_EQ(is_mark_stack_push_disallowed_.LoadRelaxed(), 0) 1070 << " " << to_ref << " " << mirror::Object::PrettyTypeOf(to_ref); 1071 Thread* self = Thread::Current(); // TODO: pass self as an argument from call sites? 1072 CHECK(thread_running_gc_ != nullptr); 1073 MarkStackMode mark_stack_mode = mark_stack_mode_.LoadRelaxed(); 1074 if (LIKELY(mark_stack_mode == kMarkStackModeThreadLocal)) { 1075 if (LIKELY(self == thread_running_gc_)) { 1076 // If GC-running thread, use the GC mark stack instead of a thread-local mark stack. 1077 CHECK(self->GetThreadLocalMarkStack() == nullptr); 1078 if (UNLIKELY(gc_mark_stack_->IsFull())) { 1079 ExpandGcMarkStack(); 1080 } 1081 gc_mark_stack_->PushBack(to_ref); 1082 } else { 1083 // Otherwise, use a thread-local mark stack. 1084 accounting::AtomicStack<mirror::Object>* tl_mark_stack = self->GetThreadLocalMarkStack(); 1085 if (UNLIKELY(tl_mark_stack == nullptr || tl_mark_stack->IsFull())) { 1086 MutexLock mu(self, mark_stack_lock_); 1087 // Get a new thread local mark stack. 1088 accounting::AtomicStack<mirror::Object>* new_tl_mark_stack; 1089 if (!pooled_mark_stacks_.empty()) { 1090 // Use a pooled mark stack. 1091 new_tl_mark_stack = pooled_mark_stacks_.back(); 1092 pooled_mark_stacks_.pop_back(); 1093 } else { 1094 // None pooled. Create a new one. 1095 new_tl_mark_stack = 1096 accounting::AtomicStack<mirror::Object>::Create( 1097 "thread local mark stack", 4 * KB, 4 * KB); 1098 } 1099 DCHECK(new_tl_mark_stack != nullptr); 1100 DCHECK(new_tl_mark_stack->IsEmpty()); 1101 new_tl_mark_stack->PushBack(to_ref); 1102 self->SetThreadLocalMarkStack(new_tl_mark_stack); 1103 if (tl_mark_stack != nullptr) { 1104 // Store the old full stack into a vector. 1105 revoked_mark_stacks_.push_back(tl_mark_stack); 1106 } 1107 } else { 1108 tl_mark_stack->PushBack(to_ref); 1109 } 1110 } 1111 } else if (mark_stack_mode == kMarkStackModeShared) { 1112 // Access the shared GC mark stack with a lock. 1113 MutexLock mu(self, mark_stack_lock_); 1114 if (UNLIKELY(gc_mark_stack_->IsFull())) { 1115 ExpandGcMarkStack(); 1116 } 1117 gc_mark_stack_->PushBack(to_ref); 1118 } else { 1119 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode), 1120 static_cast<uint32_t>(kMarkStackModeGcExclusive)) 1121 << "ref=" << to_ref 1122 << " self->gc_marking=" << self->GetIsGcMarking() 1123 << " cc->is_marking=" << is_marking_; 1124 CHECK(self == thread_running_gc_) 1125 << "Only GC-running thread should access the mark stack " 1126 << "in the GC exclusive mark stack mode"; 1127 // Access the GC mark stack without a lock. 1128 if (UNLIKELY(gc_mark_stack_->IsFull())) { 1129 ExpandGcMarkStack(); 1130 } 1131 gc_mark_stack_->PushBack(to_ref); 1132 } 1133 } 1134 1135 accounting::ObjectStack* ConcurrentCopying::GetAllocationStack() { 1136 return heap_->allocation_stack_.get(); 1137 } 1138 1139 accounting::ObjectStack* ConcurrentCopying::GetLiveStack() { 1140 return heap_->live_stack_.get(); 1141 } 1142 1143 // The following visitors are used to verify that there's no references to the from-space left after 1144 // marking. 1145 class ConcurrentCopying::VerifyNoFromSpaceRefsVisitor : public SingleRootVisitor { 1146 public: 1147 explicit VerifyNoFromSpaceRefsVisitor(ConcurrentCopying* collector) 1148 : collector_(collector) {} 1149 1150 void operator()(mirror::Object* ref, 1151 MemberOffset offset = MemberOffset(0), 1152 mirror::Object* holder = nullptr) const 1153 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1154 if (ref == nullptr) { 1155 // OK. 1156 return; 1157 } 1158 collector_->AssertToSpaceInvariant(holder, offset, ref); 1159 if (kUseBakerReadBarrier) { 1160 CHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::WhiteState()) 1161 << "Ref " << ref << " " << ref->PrettyTypeOf() 1162 << " has non-white rb_state "; 1163 } 1164 } 1165 1166 void VisitRoot(mirror::Object* root, const RootInfo& info ATTRIBUTE_UNUSED) 1167 OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) { 1168 DCHECK(root != nullptr); 1169 operator()(root); 1170 } 1171 1172 private: 1173 ConcurrentCopying* const collector_; 1174 }; 1175 1176 class ConcurrentCopying::VerifyNoFromSpaceRefsFieldVisitor { 1177 public: 1178 explicit VerifyNoFromSpaceRefsFieldVisitor(ConcurrentCopying* collector) 1179 : collector_(collector) {} 1180 1181 void operator()(ObjPtr<mirror::Object> obj, 1182 MemberOffset offset, 1183 bool is_static ATTRIBUTE_UNUSED) const 1184 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1185 mirror::Object* ref = 1186 obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(offset); 1187 VerifyNoFromSpaceRefsVisitor visitor(collector_); 1188 visitor(ref, offset, obj.Ptr()); 1189 } 1190 void operator()(ObjPtr<mirror::Class> klass, 1191 ObjPtr<mirror::Reference> ref) const 1192 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1193 CHECK(klass->IsTypeOfReferenceClass()); 1194 this->operator()(ref, mirror::Reference::ReferentOffset(), false); 1195 } 1196 1197 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 1198 REQUIRES_SHARED(Locks::mutator_lock_) { 1199 if (!root->IsNull()) { 1200 VisitRoot(root); 1201 } 1202 } 1203 1204 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 1205 REQUIRES_SHARED(Locks::mutator_lock_) { 1206 VerifyNoFromSpaceRefsVisitor visitor(collector_); 1207 visitor(root->AsMirrorPtr()); 1208 } 1209 1210 private: 1211 ConcurrentCopying* const collector_; 1212 }; 1213 1214 // Verify there's no from-space references left after the marking phase. 1215 void ConcurrentCopying::VerifyNoFromSpaceReferences() { 1216 Thread* self = Thread::Current(); 1217 DCHECK(Locks::mutator_lock_->IsExclusiveHeld(self)); 1218 // Verify all threads have is_gc_marking to be false 1219 { 1220 MutexLock mu(self, *Locks::thread_list_lock_); 1221 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1222 for (Thread* thread : thread_list) { 1223 CHECK(!thread->GetIsGcMarking()); 1224 } 1225 } 1226 1227 auto verify_no_from_space_refs_visitor = [&](mirror::Object* obj) 1228 REQUIRES_SHARED(Locks::mutator_lock_) { 1229 CHECK(obj != nullptr); 1230 space::RegionSpace* region_space = RegionSpace(); 1231 CHECK(!region_space->IsInFromSpace(obj)) << "Scanning object " << obj << " in from space"; 1232 VerifyNoFromSpaceRefsFieldVisitor visitor(this); 1233 obj->VisitReferences</*kVisitNativeRoots*/true, kDefaultVerifyFlags, kWithoutReadBarrier>( 1234 visitor, 1235 visitor); 1236 if (kUseBakerReadBarrier) { 1237 CHECK_EQ(obj->GetReadBarrierState(), ReadBarrier::WhiteState()) 1238 << "obj=" << obj << " non-white rb_state " << obj->GetReadBarrierState(); 1239 } 1240 }; 1241 // Roots. 1242 { 1243 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 1244 VerifyNoFromSpaceRefsVisitor ref_visitor(this); 1245 Runtime::Current()->VisitRoots(&ref_visitor); 1246 } 1247 // The to-space. 1248 region_space_->WalkToSpace(verify_no_from_space_refs_visitor); 1249 // Non-moving spaces. 1250 { 1251 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 1252 heap_->GetMarkBitmap()->Visit(verify_no_from_space_refs_visitor); 1253 } 1254 // The alloc stack. 1255 { 1256 VerifyNoFromSpaceRefsVisitor ref_visitor(this); 1257 for (auto* it = heap_->allocation_stack_->Begin(), *end = heap_->allocation_stack_->End(); 1258 it < end; ++it) { 1259 mirror::Object* const obj = it->AsMirrorPtr(); 1260 if (obj != nullptr && obj->GetClass() != nullptr) { 1261 // TODO: need to call this only if obj is alive? 1262 ref_visitor(obj); 1263 verify_no_from_space_refs_visitor(obj); 1264 } 1265 } 1266 } 1267 // TODO: LOS. But only refs in LOS are classes. 1268 } 1269 1270 // The following visitors are used to assert the to-space invariant. 1271 class ConcurrentCopying::AssertToSpaceInvariantRefsVisitor { 1272 public: 1273 explicit AssertToSpaceInvariantRefsVisitor(ConcurrentCopying* collector) 1274 : collector_(collector) {} 1275 1276 void operator()(mirror::Object* ref) const 1277 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1278 if (ref == nullptr) { 1279 // OK. 1280 return; 1281 } 1282 collector_->AssertToSpaceInvariant(nullptr, MemberOffset(0), ref); 1283 } 1284 1285 private: 1286 ConcurrentCopying* const collector_; 1287 }; 1288 1289 class ConcurrentCopying::AssertToSpaceInvariantFieldVisitor { 1290 public: 1291 explicit AssertToSpaceInvariantFieldVisitor(ConcurrentCopying* collector) 1292 : collector_(collector) {} 1293 1294 void operator()(ObjPtr<mirror::Object> obj, 1295 MemberOffset offset, 1296 bool is_static ATTRIBUTE_UNUSED) const 1297 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1298 mirror::Object* ref = 1299 obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(offset); 1300 AssertToSpaceInvariantRefsVisitor visitor(collector_); 1301 visitor(ref); 1302 } 1303 void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref ATTRIBUTE_UNUSED) const 1304 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1305 CHECK(klass->IsTypeOfReferenceClass()); 1306 } 1307 1308 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 1309 REQUIRES_SHARED(Locks::mutator_lock_) { 1310 if (!root->IsNull()) { 1311 VisitRoot(root); 1312 } 1313 } 1314 1315 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 1316 REQUIRES_SHARED(Locks::mutator_lock_) { 1317 AssertToSpaceInvariantRefsVisitor visitor(collector_); 1318 visitor(root->AsMirrorPtr()); 1319 } 1320 1321 private: 1322 ConcurrentCopying* const collector_; 1323 }; 1324 1325 class ConcurrentCopying::RevokeThreadLocalMarkStackCheckpoint : public Closure { 1326 public: 1327 RevokeThreadLocalMarkStackCheckpoint(ConcurrentCopying* concurrent_copying, 1328 bool disable_weak_ref_access) 1329 : concurrent_copying_(concurrent_copying), 1330 disable_weak_ref_access_(disable_weak_ref_access) { 1331 } 1332 1333 virtual void Run(Thread* thread) OVERRIDE NO_THREAD_SAFETY_ANALYSIS { 1334 // Note: self is not necessarily equal to thread since thread may be suspended. 1335 Thread* self = Thread::Current(); 1336 CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 1337 << thread->GetState() << " thread " << thread << " self " << self; 1338 // Revoke thread local mark stacks. 1339 accounting::AtomicStack<mirror::Object>* tl_mark_stack = thread->GetThreadLocalMarkStack(); 1340 if (tl_mark_stack != nullptr) { 1341 MutexLock mu(self, concurrent_copying_->mark_stack_lock_); 1342 concurrent_copying_->revoked_mark_stacks_.push_back(tl_mark_stack); 1343 thread->SetThreadLocalMarkStack(nullptr); 1344 } 1345 // Disable weak ref access. 1346 if (disable_weak_ref_access_) { 1347 thread->SetWeakRefAccessEnabled(false); 1348 } 1349 // If thread is a running mutator, then act on behalf of the garbage collector. 1350 // See the code in ThreadList::RunCheckpoint. 1351 concurrent_copying_->GetBarrier().Pass(self); 1352 } 1353 1354 private: 1355 ConcurrentCopying* const concurrent_copying_; 1356 const bool disable_weak_ref_access_; 1357 }; 1358 1359 void ConcurrentCopying::RevokeThreadLocalMarkStacks(bool disable_weak_ref_access, 1360 Closure* checkpoint_callback) { 1361 Thread* self = Thread::Current(); 1362 RevokeThreadLocalMarkStackCheckpoint check_point(this, disable_weak_ref_access); 1363 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 1364 gc_barrier_->Init(self, 0); 1365 size_t barrier_count = thread_list->RunCheckpoint(&check_point, checkpoint_callback); 1366 // If there are no threads to wait which implys that all the checkpoint functions are finished, 1367 // then no need to release the mutator lock. 1368 if (barrier_count == 0) { 1369 return; 1370 } 1371 Locks::mutator_lock_->SharedUnlock(self); 1372 { 1373 ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun); 1374 gc_barrier_->Increment(self, barrier_count); 1375 } 1376 Locks::mutator_lock_->SharedLock(self); 1377 } 1378 1379 void ConcurrentCopying::RevokeThreadLocalMarkStack(Thread* thread) { 1380 Thread* self = Thread::Current(); 1381 CHECK_EQ(self, thread); 1382 accounting::AtomicStack<mirror::Object>* tl_mark_stack = thread->GetThreadLocalMarkStack(); 1383 if (tl_mark_stack != nullptr) { 1384 CHECK(is_marking_); 1385 MutexLock mu(self, mark_stack_lock_); 1386 revoked_mark_stacks_.push_back(tl_mark_stack); 1387 thread->SetThreadLocalMarkStack(nullptr); 1388 } 1389 } 1390 1391 void ConcurrentCopying::ProcessMarkStack() { 1392 if (kVerboseMode) { 1393 LOG(INFO) << "ProcessMarkStack. "; 1394 } 1395 bool empty_prev = false; 1396 while (true) { 1397 bool empty = ProcessMarkStackOnce(); 1398 if (empty_prev && empty) { 1399 // Saw empty mark stack for a second time, done. 1400 break; 1401 } 1402 empty_prev = empty; 1403 } 1404 } 1405 1406 bool ConcurrentCopying::ProcessMarkStackOnce() { 1407 Thread* self = Thread::Current(); 1408 CHECK(thread_running_gc_ != nullptr); 1409 CHECK(self == thread_running_gc_); 1410 CHECK(self->GetThreadLocalMarkStack() == nullptr); 1411 size_t count = 0; 1412 MarkStackMode mark_stack_mode = mark_stack_mode_.LoadRelaxed(); 1413 if (mark_stack_mode == kMarkStackModeThreadLocal) { 1414 // Process the thread-local mark stacks and the GC mark stack. 1415 count += ProcessThreadLocalMarkStacks(false, nullptr); 1416 while (!gc_mark_stack_->IsEmpty()) { 1417 mirror::Object* to_ref = gc_mark_stack_->PopBack(); 1418 ProcessMarkStackRef(to_ref); 1419 ++count; 1420 } 1421 gc_mark_stack_->Reset(); 1422 } else if (mark_stack_mode == kMarkStackModeShared) { 1423 // Do an empty checkpoint to avoid a race with a mutator preempted in the middle of a read 1424 // barrier but before pushing onto the mark stack. b/32508093. Note the weak ref access is 1425 // disabled at this point. 1426 IssueEmptyCheckpoint(); 1427 // Process the shared GC mark stack with a lock. 1428 { 1429 MutexLock mu(self, mark_stack_lock_); 1430 CHECK(revoked_mark_stacks_.empty()); 1431 } 1432 while (true) { 1433 std::vector<mirror::Object*> refs; 1434 { 1435 // Copy refs with lock. Note the number of refs should be small. 1436 MutexLock mu(self, mark_stack_lock_); 1437 if (gc_mark_stack_->IsEmpty()) { 1438 break; 1439 } 1440 for (StackReference<mirror::Object>* p = gc_mark_stack_->Begin(); 1441 p != gc_mark_stack_->End(); ++p) { 1442 refs.push_back(p->AsMirrorPtr()); 1443 } 1444 gc_mark_stack_->Reset(); 1445 } 1446 for (mirror::Object* ref : refs) { 1447 ProcessMarkStackRef(ref); 1448 ++count; 1449 } 1450 } 1451 } else { 1452 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode), 1453 static_cast<uint32_t>(kMarkStackModeGcExclusive)); 1454 { 1455 MutexLock mu(self, mark_stack_lock_); 1456 CHECK(revoked_mark_stacks_.empty()); 1457 } 1458 // Process the GC mark stack in the exclusive mode. No need to take the lock. 1459 while (!gc_mark_stack_->IsEmpty()) { 1460 mirror::Object* to_ref = gc_mark_stack_->PopBack(); 1461 ProcessMarkStackRef(to_ref); 1462 ++count; 1463 } 1464 gc_mark_stack_->Reset(); 1465 } 1466 1467 // Return true if the stack was empty. 1468 return count == 0; 1469 } 1470 1471 size_t ConcurrentCopying::ProcessThreadLocalMarkStacks(bool disable_weak_ref_access, 1472 Closure* checkpoint_callback) { 1473 // Run a checkpoint to collect all thread local mark stacks and iterate over them all. 1474 RevokeThreadLocalMarkStacks(disable_weak_ref_access, checkpoint_callback); 1475 size_t count = 0; 1476 std::vector<accounting::AtomicStack<mirror::Object>*> mark_stacks; 1477 { 1478 MutexLock mu(Thread::Current(), mark_stack_lock_); 1479 // Make a copy of the mark stack vector. 1480 mark_stacks = revoked_mark_stacks_; 1481 revoked_mark_stacks_.clear(); 1482 } 1483 for (accounting::AtomicStack<mirror::Object>* mark_stack : mark_stacks) { 1484 for (StackReference<mirror::Object>* p = mark_stack->Begin(); p != mark_stack->End(); ++p) { 1485 mirror::Object* to_ref = p->AsMirrorPtr(); 1486 ProcessMarkStackRef(to_ref); 1487 ++count; 1488 } 1489 { 1490 MutexLock mu(Thread::Current(), mark_stack_lock_); 1491 if (pooled_mark_stacks_.size() >= kMarkStackPoolSize) { 1492 // The pool has enough. Delete it. 1493 delete mark_stack; 1494 } else { 1495 // Otherwise, put it into the pool for later reuse. 1496 mark_stack->Reset(); 1497 pooled_mark_stacks_.push_back(mark_stack); 1498 } 1499 } 1500 } 1501 return count; 1502 } 1503 1504 inline void ConcurrentCopying::ProcessMarkStackRef(mirror::Object* to_ref) { 1505 DCHECK(!region_space_->IsInFromSpace(to_ref)); 1506 if (kUseBakerReadBarrier) { 1507 DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState()) 1508 << " " << to_ref << " " << to_ref->GetReadBarrierState() 1509 << " is_marked=" << IsMarked(to_ref); 1510 } 1511 bool add_to_live_bytes = false; 1512 if (region_space_->IsInUnevacFromSpace(to_ref)) { 1513 // Mark the bitmap only in the GC thread here so that we don't need a CAS. 1514 if (!kUseBakerReadBarrier || !region_space_bitmap_->Set(to_ref)) { 1515 // It may be already marked if we accidentally pushed the same object twice due to the racy 1516 // bitmap read in MarkUnevacFromSpaceRegion. 1517 Scan(to_ref); 1518 // Only add to the live bytes if the object was not already marked. 1519 add_to_live_bytes = true; 1520 } 1521 } else { 1522 Scan(to_ref); 1523 } 1524 if (kUseBakerReadBarrier) { 1525 DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState()) 1526 << " " << to_ref << " " << to_ref->GetReadBarrierState() 1527 << " is_marked=" << IsMarked(to_ref); 1528 } 1529 #ifdef USE_BAKER_OR_BROOKS_READ_BARRIER 1530 mirror::Object* referent = nullptr; 1531 if (UNLIKELY((to_ref->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass() && 1532 (referent = to_ref->AsReference()->GetReferent<kWithoutReadBarrier>()) != nullptr && 1533 !IsInToSpace(referent)))) { 1534 // Leave this reference gray in the queue so that GetReferent() will trigger a read barrier. We 1535 // will change it to white later in ReferenceQueue::DequeuePendingReference(). 1536 DCHECK(to_ref->AsReference()->GetPendingNext() != nullptr) << "Left unenqueued ref gray " << to_ref; 1537 } else { 1538 // We may occasionally leave a reference white in the queue if its referent happens to be 1539 // concurrently marked after the Scan() call above has enqueued the Reference, in which case the 1540 // above IsInToSpace() evaluates to true and we change the color from gray to white here in this 1541 // else block. 1542 if (kUseBakerReadBarrier) { 1543 bool success = to_ref->AtomicSetReadBarrierState</*kCasRelease*/true>( 1544 ReadBarrier::GrayState(), 1545 ReadBarrier::WhiteState()); 1546 DCHECK(success) << "Must succeed as we won the race."; 1547 } 1548 } 1549 #else 1550 DCHECK(!kUseBakerReadBarrier); 1551 #endif 1552 1553 if (add_to_live_bytes) { 1554 // Add to the live bytes per unevacuated from space. Note this code is always run by the 1555 // GC-running thread (no synchronization required). 1556 DCHECK(region_space_bitmap_->Test(to_ref)); 1557 size_t obj_size = to_ref->SizeOf<kDefaultVerifyFlags>(); 1558 size_t alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment); 1559 region_space_->AddLiveBytes(to_ref, alloc_size); 1560 } 1561 if (ReadBarrier::kEnableToSpaceInvariantChecks) { 1562 CHECK(to_ref != nullptr); 1563 space::RegionSpace* region_space = RegionSpace(); 1564 CHECK(!region_space->IsInFromSpace(to_ref)) << "Scanning object " << to_ref << " in from space"; 1565 AssertToSpaceInvariant(nullptr, MemberOffset(0), to_ref); 1566 AssertToSpaceInvariantFieldVisitor visitor(this); 1567 to_ref->VisitReferences</*kVisitNativeRoots*/true, kDefaultVerifyFlags, kWithoutReadBarrier>( 1568 visitor, 1569 visitor); 1570 } 1571 } 1572 1573 class ConcurrentCopying::DisableWeakRefAccessCallback : public Closure { 1574 public: 1575 explicit DisableWeakRefAccessCallback(ConcurrentCopying* concurrent_copying) 1576 : concurrent_copying_(concurrent_copying) { 1577 } 1578 1579 void Run(Thread* self ATTRIBUTE_UNUSED) OVERRIDE REQUIRES(Locks::thread_list_lock_) { 1580 // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint() 1581 // to avoid a deadlock b/31500969. 1582 CHECK(concurrent_copying_->weak_ref_access_enabled_); 1583 concurrent_copying_->weak_ref_access_enabled_ = false; 1584 } 1585 1586 private: 1587 ConcurrentCopying* const concurrent_copying_; 1588 }; 1589 1590 void ConcurrentCopying::SwitchToSharedMarkStackMode() { 1591 Thread* self = Thread::Current(); 1592 CHECK(thread_running_gc_ != nullptr); 1593 CHECK_EQ(self, thread_running_gc_); 1594 CHECK(self->GetThreadLocalMarkStack() == nullptr); 1595 MarkStackMode before_mark_stack_mode = mark_stack_mode_.LoadRelaxed(); 1596 CHECK_EQ(static_cast<uint32_t>(before_mark_stack_mode), 1597 static_cast<uint32_t>(kMarkStackModeThreadLocal)); 1598 mark_stack_mode_.StoreRelaxed(kMarkStackModeShared); 1599 DisableWeakRefAccessCallback dwrac(this); 1600 // Process the thread local mark stacks one last time after switching to the shared mark stack 1601 // mode and disable weak ref accesses. 1602 ProcessThreadLocalMarkStacks(true, &dwrac); 1603 if (kVerboseMode) { 1604 LOG(INFO) << "Switched to shared mark stack mode and disabled weak ref access"; 1605 } 1606 } 1607 1608 void ConcurrentCopying::SwitchToGcExclusiveMarkStackMode() { 1609 Thread* self = Thread::Current(); 1610 CHECK(thread_running_gc_ != nullptr); 1611 CHECK_EQ(self, thread_running_gc_); 1612 CHECK(self->GetThreadLocalMarkStack() == nullptr); 1613 MarkStackMode before_mark_stack_mode = mark_stack_mode_.LoadRelaxed(); 1614 CHECK_EQ(static_cast<uint32_t>(before_mark_stack_mode), 1615 static_cast<uint32_t>(kMarkStackModeShared)); 1616 mark_stack_mode_.StoreRelaxed(kMarkStackModeGcExclusive); 1617 QuasiAtomic::ThreadFenceForConstructor(); 1618 if (kVerboseMode) { 1619 LOG(INFO) << "Switched to GC exclusive mark stack mode"; 1620 } 1621 } 1622 1623 void ConcurrentCopying::CheckEmptyMarkStack() { 1624 Thread* self = Thread::Current(); 1625 CHECK(thread_running_gc_ != nullptr); 1626 CHECK_EQ(self, thread_running_gc_); 1627 CHECK(self->GetThreadLocalMarkStack() == nullptr); 1628 MarkStackMode mark_stack_mode = mark_stack_mode_.LoadRelaxed(); 1629 if (mark_stack_mode == kMarkStackModeThreadLocal) { 1630 // Thread-local mark stack mode. 1631 RevokeThreadLocalMarkStacks(false, nullptr); 1632 MutexLock mu(Thread::Current(), mark_stack_lock_); 1633 if (!revoked_mark_stacks_.empty()) { 1634 for (accounting::AtomicStack<mirror::Object>* mark_stack : revoked_mark_stacks_) { 1635 while (!mark_stack->IsEmpty()) { 1636 mirror::Object* obj = mark_stack->PopBack(); 1637 if (kUseBakerReadBarrier) { 1638 uint32_t rb_state = obj->GetReadBarrierState(); 1639 LOG(INFO) << "On mark queue : " << obj << " " << obj->PrettyTypeOf() << " rb_state=" 1640 << rb_state << " is_marked=" << IsMarked(obj); 1641 } else { 1642 LOG(INFO) << "On mark queue : " << obj << " " << obj->PrettyTypeOf() 1643 << " is_marked=" << IsMarked(obj); 1644 } 1645 } 1646 } 1647 LOG(FATAL) << "mark stack is not empty"; 1648 } 1649 } else { 1650 // Shared, GC-exclusive, or off. 1651 MutexLock mu(Thread::Current(), mark_stack_lock_); 1652 CHECK(gc_mark_stack_->IsEmpty()); 1653 CHECK(revoked_mark_stacks_.empty()); 1654 } 1655 } 1656 1657 void ConcurrentCopying::SweepSystemWeaks(Thread* self) { 1658 TimingLogger::ScopedTiming split("SweepSystemWeaks", GetTimings()); 1659 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 1660 Runtime::Current()->SweepSystemWeaks(this); 1661 } 1662 1663 void ConcurrentCopying::Sweep(bool swap_bitmaps) { 1664 { 1665 TimingLogger::ScopedTiming t("MarkStackAsLive", GetTimings()); 1666 accounting::ObjectStack* live_stack = heap_->GetLiveStack(); 1667 if (kEnableFromSpaceAccountingCheck) { 1668 CHECK_GE(live_stack_freeze_size_, live_stack->Size()); 1669 } 1670 heap_->MarkAllocStackAsLive(live_stack); 1671 live_stack->Reset(); 1672 } 1673 CheckEmptyMarkStack(); 1674 TimingLogger::ScopedTiming split("Sweep", GetTimings()); 1675 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1676 if (space->IsContinuousMemMapAllocSpace()) { 1677 space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace(); 1678 if (space == region_space_ || immune_spaces_.ContainsSpace(space)) { 1679 continue; 1680 } 1681 TimingLogger::ScopedTiming split2( 1682 alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings()); 1683 RecordFree(alloc_space->Sweep(swap_bitmaps)); 1684 } 1685 } 1686 SweepLargeObjects(swap_bitmaps); 1687 } 1688 1689 void ConcurrentCopying::MarkZygoteLargeObjects() { 1690 TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings()); 1691 Thread* const self = Thread::Current(); 1692 WriterMutexLock rmu(self, *Locks::heap_bitmap_lock_); 1693 space::LargeObjectSpace* const los = heap_->GetLargeObjectsSpace(); 1694 if (los != nullptr) { 1695 // Pick the current live bitmap (mark bitmap if swapped). 1696 accounting::LargeObjectBitmap* const live_bitmap = los->GetLiveBitmap(); 1697 accounting::LargeObjectBitmap* const mark_bitmap = los->GetMarkBitmap(); 1698 // Walk through all of the objects and explicitly mark the zygote ones so they don't get swept. 1699 std::pair<uint8_t*, uint8_t*> range = los->GetBeginEndAtomic(); 1700 live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(range.first), 1701 reinterpret_cast<uintptr_t>(range.second), 1702 [mark_bitmap, los, self](mirror::Object* obj) 1703 REQUIRES(Locks::heap_bitmap_lock_) 1704 REQUIRES_SHARED(Locks::mutator_lock_) { 1705 if (los->IsZygoteLargeObject(self, obj)) { 1706 mark_bitmap->Set(obj); 1707 } 1708 }); 1709 } 1710 } 1711 1712 void ConcurrentCopying::SweepLargeObjects(bool swap_bitmaps) { 1713 TimingLogger::ScopedTiming split("SweepLargeObjects", GetTimings()); 1714 if (heap_->GetLargeObjectsSpace() != nullptr) { 1715 RecordFreeLOS(heap_->GetLargeObjectsSpace()->Sweep(swap_bitmaps)); 1716 } 1717 } 1718 1719 void ConcurrentCopying::ReclaimPhase() { 1720 TimingLogger::ScopedTiming split("ReclaimPhase", GetTimings()); 1721 if (kVerboseMode) { 1722 LOG(INFO) << "GC ReclaimPhase"; 1723 } 1724 Thread* self = Thread::Current(); 1725 1726 { 1727 // Double-check that the mark stack is empty. 1728 // Note: need to set this after VerifyNoFromSpaceRef(). 1729 is_asserting_to_space_invariant_ = false; 1730 QuasiAtomic::ThreadFenceForConstructor(); 1731 if (kVerboseMode) { 1732 LOG(INFO) << "Issue an empty check point. "; 1733 } 1734 IssueEmptyCheckpoint(); 1735 // Disable the check. 1736 is_mark_stack_push_disallowed_.StoreSequentiallyConsistent(0); 1737 if (kUseBakerReadBarrier) { 1738 updated_all_immune_objects_.StoreSequentiallyConsistent(false); 1739 } 1740 CheckEmptyMarkStack(); 1741 } 1742 1743 { 1744 // Record freed objects. 1745 TimingLogger::ScopedTiming split2("RecordFree", GetTimings()); 1746 // Don't include thread-locals that are in the to-space. 1747 const uint64_t from_bytes = region_space_->GetBytesAllocatedInFromSpace(); 1748 const uint64_t from_objects = region_space_->GetObjectsAllocatedInFromSpace(); 1749 const uint64_t unevac_from_bytes = region_space_->GetBytesAllocatedInUnevacFromSpace(); 1750 const uint64_t unevac_from_objects = region_space_->GetObjectsAllocatedInUnevacFromSpace(); 1751 uint64_t to_bytes = bytes_moved_.LoadSequentiallyConsistent(); 1752 cumulative_bytes_moved_.FetchAndAddRelaxed(to_bytes); 1753 uint64_t to_objects = objects_moved_.LoadSequentiallyConsistent(); 1754 cumulative_objects_moved_.FetchAndAddRelaxed(to_objects); 1755 if (kEnableFromSpaceAccountingCheck) { 1756 CHECK_EQ(from_space_num_objects_at_first_pause_, from_objects + unevac_from_objects); 1757 CHECK_EQ(from_space_num_bytes_at_first_pause_, from_bytes + unevac_from_bytes); 1758 } 1759 CHECK_LE(to_objects, from_objects); 1760 CHECK_LE(to_bytes, from_bytes); 1761 // cleared_bytes and cleared_objects may be greater than the from space equivalents since 1762 // ClearFromSpace may clear empty unevac regions. 1763 uint64_t cleared_bytes; 1764 uint64_t cleared_objects; 1765 { 1766 TimingLogger::ScopedTiming split4("ClearFromSpace", GetTimings()); 1767 region_space_->ClearFromSpace(&cleared_bytes, &cleared_objects); 1768 CHECK_GE(cleared_bytes, from_bytes); 1769 CHECK_GE(cleared_objects, from_objects); 1770 } 1771 int64_t freed_bytes = cleared_bytes - to_bytes; 1772 int64_t freed_objects = cleared_objects - to_objects; 1773 if (kVerboseMode) { 1774 LOG(INFO) << "RecordFree:" 1775 << " from_bytes=" << from_bytes << " from_objects=" << from_objects 1776 << " unevac_from_bytes=" << unevac_from_bytes << " unevac_from_objects=" << unevac_from_objects 1777 << " to_bytes=" << to_bytes << " to_objects=" << to_objects 1778 << " freed_bytes=" << freed_bytes << " freed_objects=" << freed_objects 1779 << " from_space size=" << region_space_->FromSpaceSize() 1780 << " unevac_from_space size=" << region_space_->UnevacFromSpaceSize() 1781 << " to_space size=" << region_space_->ToSpaceSize(); 1782 LOG(INFO) << "(before) num_bytes_allocated=" << heap_->num_bytes_allocated_.LoadSequentiallyConsistent(); 1783 } 1784 RecordFree(ObjectBytePair(freed_objects, freed_bytes)); 1785 if (kVerboseMode) { 1786 LOG(INFO) << "(after) num_bytes_allocated=" << heap_->num_bytes_allocated_.LoadSequentiallyConsistent(); 1787 } 1788 } 1789 1790 { 1791 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 1792 Sweep(false); 1793 SwapBitmaps(); 1794 heap_->UnBindBitmaps(); 1795 1796 // The bitmap was cleared at the start of the GC, there is nothing we need to do here. 1797 DCHECK(region_space_bitmap_ != nullptr); 1798 region_space_bitmap_ = nullptr; 1799 } 1800 1801 CheckEmptyMarkStack(); 1802 1803 if (kVerboseMode) { 1804 LOG(INFO) << "GC end of ReclaimPhase"; 1805 } 1806 } 1807 1808 // Assert the to-space invariant. 1809 void ConcurrentCopying::AssertToSpaceInvariant(mirror::Object* obj, 1810 MemberOffset offset, 1811 mirror::Object* ref) { 1812 CHECK_EQ(heap_->collector_type_, kCollectorTypeCC); 1813 if (is_asserting_to_space_invariant_) { 1814 using RegionType = space::RegionSpace::RegionType; 1815 space::RegionSpace::RegionType type = region_space_->GetRegionType(ref); 1816 if (type == RegionType::kRegionTypeToSpace) { 1817 // OK. 1818 return; 1819 } else if (type == RegionType::kRegionTypeUnevacFromSpace) { 1820 CHECK(IsMarkedInUnevacFromSpace(ref)) << ref; 1821 } else if (UNLIKELY(type == RegionType::kRegionTypeFromSpace)) { 1822 // Not OK. Do extra logging. 1823 if (obj != nullptr) { 1824 LogFromSpaceRefHolder(obj, offset); 1825 } 1826 ref->GetLockWord(false).Dump(LOG_STREAM(FATAL_WITHOUT_ABORT)); 1827 CHECK(false) << "Found from-space ref " << ref << " " << ref->PrettyTypeOf(); 1828 } else { 1829 AssertToSpaceInvariantInNonMovingSpace(obj, ref); 1830 } 1831 } 1832 } 1833 1834 class RootPrinter { 1835 public: 1836 RootPrinter() { } 1837 1838 template <class MirrorType> 1839 ALWAYS_INLINE void VisitRootIfNonNull(mirror::CompressedReference<MirrorType>* root) 1840 REQUIRES_SHARED(Locks::mutator_lock_) { 1841 if (!root->IsNull()) { 1842 VisitRoot(root); 1843 } 1844 } 1845 1846 template <class MirrorType> 1847 void VisitRoot(mirror::Object** root) 1848 REQUIRES_SHARED(Locks::mutator_lock_) { 1849 LOG(FATAL_WITHOUT_ABORT) << "root=" << root << " ref=" << *root; 1850 } 1851 1852 template <class MirrorType> 1853 void VisitRoot(mirror::CompressedReference<MirrorType>* root) 1854 REQUIRES_SHARED(Locks::mutator_lock_) { 1855 LOG(FATAL_WITHOUT_ABORT) << "root=" << root << " ref=" << root->AsMirrorPtr(); 1856 } 1857 }; 1858 1859 void ConcurrentCopying::AssertToSpaceInvariant(GcRootSource* gc_root_source, 1860 mirror::Object* ref) { 1861 CHECK(heap_->collector_type_ == kCollectorTypeCC) << static_cast<size_t>(heap_->collector_type_); 1862 if (is_asserting_to_space_invariant_) { 1863 if (region_space_->IsInToSpace(ref)) { 1864 // OK. 1865 return; 1866 } else if (region_space_->IsInUnevacFromSpace(ref)) { 1867 CHECK(IsMarkedInUnevacFromSpace(ref)) << ref; 1868 } else if (region_space_->IsInFromSpace(ref)) { 1869 // Not OK. Do extra logging. 1870 if (gc_root_source == nullptr) { 1871 // No info. 1872 } else if (gc_root_source->HasArtField()) { 1873 ArtField* field = gc_root_source->GetArtField(); 1874 LOG(FATAL_WITHOUT_ABORT) << "gc root in field " << field << " " 1875 << ArtField::PrettyField(field); 1876 RootPrinter root_printer; 1877 field->VisitRoots(root_printer); 1878 } else if (gc_root_source->HasArtMethod()) { 1879 ArtMethod* method = gc_root_source->GetArtMethod(); 1880 LOG(FATAL_WITHOUT_ABORT) << "gc root in method " << method << " " 1881 << ArtMethod::PrettyMethod(method); 1882 RootPrinter root_printer; 1883 method->VisitRoots(root_printer, kRuntimePointerSize); 1884 } 1885 ref->GetLockWord(false).Dump(LOG_STREAM(FATAL_WITHOUT_ABORT)); 1886 region_space_->DumpNonFreeRegions(LOG_STREAM(FATAL_WITHOUT_ABORT)); 1887 PrintFileToLog("/proc/self/maps", LogSeverity::FATAL_WITHOUT_ABORT); 1888 MemMap::DumpMaps(LOG_STREAM(FATAL_WITHOUT_ABORT), true); 1889 CHECK(false) << "Found from-space ref " << ref << " " << ref->PrettyTypeOf(); 1890 } else { 1891 AssertToSpaceInvariantInNonMovingSpace(nullptr, ref); 1892 } 1893 } 1894 } 1895 1896 void ConcurrentCopying::LogFromSpaceRefHolder(mirror::Object* obj, MemberOffset offset) { 1897 if (kUseBakerReadBarrier) { 1898 LOG(INFO) << "holder=" << obj << " " << obj->PrettyTypeOf() 1899 << " holder rb_state=" << obj->GetReadBarrierState(); 1900 } else { 1901 LOG(INFO) << "holder=" << obj << " " << obj->PrettyTypeOf(); 1902 } 1903 if (region_space_->IsInFromSpace(obj)) { 1904 LOG(INFO) << "holder is in the from-space."; 1905 } else if (region_space_->IsInToSpace(obj)) { 1906 LOG(INFO) << "holder is in the to-space."; 1907 } else if (region_space_->IsInUnevacFromSpace(obj)) { 1908 LOG(INFO) << "holder is in the unevac from-space."; 1909 if (IsMarkedInUnevacFromSpace(obj)) { 1910 LOG(INFO) << "holder is marked in the region space bitmap."; 1911 } else { 1912 LOG(INFO) << "holder is not marked in the region space bitmap."; 1913 } 1914 } else { 1915 // In a non-moving space. 1916 if (immune_spaces_.ContainsObject(obj)) { 1917 LOG(INFO) << "holder is in an immune image or the zygote space."; 1918 } else { 1919 LOG(INFO) << "holder is in a non-immune, non-moving (or main) space."; 1920 accounting::ContinuousSpaceBitmap* mark_bitmap = 1921 heap_mark_bitmap_->GetContinuousSpaceBitmap(obj); 1922 accounting::LargeObjectBitmap* los_bitmap = 1923 heap_mark_bitmap_->GetLargeObjectBitmap(obj); 1924 CHECK(los_bitmap != nullptr) << "LOS bitmap covers the entire address range"; 1925 bool is_los = mark_bitmap == nullptr; 1926 if (!is_los && mark_bitmap->Test(obj)) { 1927 LOG(INFO) << "holder is marked in the mark bit map."; 1928 } else if (is_los && los_bitmap->Test(obj)) { 1929 LOG(INFO) << "holder is marked in the los bit map."; 1930 } else { 1931 // If ref is on the allocation stack, then it is considered 1932 // mark/alive (but not necessarily on the live stack.) 1933 if (IsOnAllocStack(obj)) { 1934 LOG(INFO) << "holder is on the alloc stack."; 1935 } else { 1936 LOG(INFO) << "holder is not marked or on the alloc stack."; 1937 } 1938 } 1939 } 1940 } 1941 LOG(INFO) << "offset=" << offset.SizeValue(); 1942 } 1943 1944 void ConcurrentCopying::AssertToSpaceInvariantInNonMovingSpace(mirror::Object* obj, 1945 mirror::Object* ref) { 1946 // In a non-moving spaces. Check that the ref is marked. 1947 if (immune_spaces_.ContainsObject(ref)) { 1948 if (kUseBakerReadBarrier) { 1949 // Immune object may not be gray if called from the GC. 1950 if (Thread::Current() == thread_running_gc_ && !gc_grays_immune_objects_) { 1951 return; 1952 } 1953 bool updated_all_immune_objects = updated_all_immune_objects_.LoadSequentiallyConsistent(); 1954 CHECK(updated_all_immune_objects || ref->GetReadBarrierState() == ReadBarrier::GrayState()) 1955 << "Unmarked immune space ref. obj=" << obj << " rb_state=" 1956 << (obj != nullptr ? obj->GetReadBarrierState() : 0U) 1957 << " ref=" << ref << " ref rb_state=" << ref->GetReadBarrierState() 1958 << " updated_all_immune_objects=" << updated_all_immune_objects; 1959 } 1960 } else { 1961 accounting::ContinuousSpaceBitmap* mark_bitmap = 1962 heap_mark_bitmap_->GetContinuousSpaceBitmap(ref); 1963 accounting::LargeObjectBitmap* los_bitmap = 1964 heap_mark_bitmap_->GetLargeObjectBitmap(ref); 1965 bool is_los = mark_bitmap == nullptr; 1966 if ((!is_los && mark_bitmap->Test(ref)) || 1967 (is_los && los_bitmap->Test(ref))) { 1968 // OK. 1969 } else { 1970 // If ref is on the allocation stack, then it may not be 1971 // marked live, but considered marked/alive (but not 1972 // necessarily on the live stack). 1973 CHECK(IsOnAllocStack(ref)) << "Unmarked ref that's not on the allocation stack. " 1974 << "obj=" << obj << " ref=" << ref; 1975 } 1976 } 1977 } 1978 1979 // Used to scan ref fields of an object. 1980 class ConcurrentCopying::RefFieldsVisitor { 1981 public: 1982 explicit RefFieldsVisitor(ConcurrentCopying* collector) 1983 : collector_(collector) {} 1984 1985 void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */) 1986 const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_) 1987 REQUIRES_SHARED(Locks::heap_bitmap_lock_) { 1988 collector_->Process(obj, offset); 1989 } 1990 1991 void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const 1992 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE { 1993 CHECK(klass->IsTypeOfReferenceClass()); 1994 collector_->DelayReferenceReferent(klass, ref); 1995 } 1996 1997 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 1998 ALWAYS_INLINE 1999 REQUIRES_SHARED(Locks::mutator_lock_) { 2000 if (!root->IsNull()) { 2001 VisitRoot(root); 2002 } 2003 } 2004 2005 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 2006 ALWAYS_INLINE 2007 REQUIRES_SHARED(Locks::mutator_lock_) { 2008 collector_->MarkRoot</*kGrayImmuneObject*/false>(root); 2009 } 2010 2011 private: 2012 ConcurrentCopying* const collector_; 2013 }; 2014 2015 // Scan ref fields of an object. 2016 inline void ConcurrentCopying::Scan(mirror::Object* to_ref) { 2017 if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) { 2018 // Avoid all read barriers during visit references to help performance. 2019 // Don't do this in transaction mode because we may read the old value of an field which may 2020 // trigger read barriers. 2021 Thread::Current()->ModifyDebugDisallowReadBarrier(1); 2022 } 2023 DCHECK(!region_space_->IsInFromSpace(to_ref)); 2024 DCHECK_EQ(Thread::Current(), thread_running_gc_); 2025 RefFieldsVisitor visitor(this); 2026 // Disable the read barrier for a performance reason. 2027 to_ref->VisitReferences</*kVisitNativeRoots*/true, kDefaultVerifyFlags, kWithoutReadBarrier>( 2028 visitor, visitor); 2029 if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) { 2030 Thread::Current()->ModifyDebugDisallowReadBarrier(-1); 2031 } 2032 } 2033 2034 // Process a field. 2035 inline void ConcurrentCopying::Process(mirror::Object* obj, MemberOffset offset) { 2036 DCHECK_EQ(Thread::Current(), thread_running_gc_); 2037 mirror::Object* ref = obj->GetFieldObject< 2038 mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset); 2039 mirror::Object* to_ref = Mark</*kGrayImmuneObject*/false, /*kFromGCThread*/true>( 2040 ref, 2041 /*holder*/ obj, 2042 offset); 2043 if (to_ref == ref) { 2044 return; 2045 } 2046 // This may fail if the mutator writes to the field at the same time. But it's ok. 2047 mirror::Object* expected_ref = ref; 2048 mirror::Object* new_ref = to_ref; 2049 do { 2050 if (expected_ref != 2051 obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset)) { 2052 // It was updated by the mutator. 2053 break; 2054 } 2055 // Use release cas to make sure threads reading the reference see contents of copied objects. 2056 } while (!obj->CasFieldWeakReleaseObjectWithoutWriteBarrier<false, false, kVerifyNone>( 2057 offset, 2058 expected_ref, 2059 new_ref)); 2060 } 2061 2062 // Process some roots. 2063 inline void ConcurrentCopying::VisitRoots( 2064 mirror::Object*** roots, size_t count, const RootInfo& info ATTRIBUTE_UNUSED) { 2065 for (size_t i = 0; i < count; ++i) { 2066 mirror::Object** root = roots[i]; 2067 mirror::Object* ref = *root; 2068 mirror::Object* to_ref = Mark(ref); 2069 if (to_ref == ref) { 2070 continue; 2071 } 2072 Atomic<mirror::Object*>* addr = reinterpret_cast<Atomic<mirror::Object*>*>(root); 2073 mirror::Object* expected_ref = ref; 2074 mirror::Object* new_ref = to_ref; 2075 do { 2076 if (expected_ref != addr->LoadRelaxed()) { 2077 // It was updated by the mutator. 2078 break; 2079 } 2080 } while (!addr->CompareExchangeWeakRelaxed(expected_ref, new_ref)); 2081 } 2082 } 2083 2084 template<bool kGrayImmuneObject> 2085 inline void ConcurrentCopying::MarkRoot(mirror::CompressedReference<mirror::Object>* root) { 2086 DCHECK(!root->IsNull()); 2087 mirror::Object* const ref = root->AsMirrorPtr(); 2088 mirror::Object* to_ref = Mark<kGrayImmuneObject>(ref); 2089 if (to_ref != ref) { 2090 auto* addr = reinterpret_cast<Atomic<mirror::CompressedReference<mirror::Object>>*>(root); 2091 auto expected_ref = mirror::CompressedReference<mirror::Object>::FromMirrorPtr(ref); 2092 auto new_ref = mirror::CompressedReference<mirror::Object>::FromMirrorPtr(to_ref); 2093 // If the cas fails, then it was updated by the mutator. 2094 do { 2095 if (ref != addr->LoadRelaxed().AsMirrorPtr()) { 2096 // It was updated by the mutator. 2097 break; 2098 } 2099 } while (!addr->CompareExchangeWeakRelaxed(expected_ref, new_ref)); 2100 } 2101 } 2102 2103 inline void ConcurrentCopying::VisitRoots( 2104 mirror::CompressedReference<mirror::Object>** roots, size_t count, 2105 const RootInfo& info ATTRIBUTE_UNUSED) { 2106 for (size_t i = 0; i < count; ++i) { 2107 mirror::CompressedReference<mirror::Object>* const root = roots[i]; 2108 if (!root->IsNull()) { 2109 // kGrayImmuneObject is true because this is used for the thread flip. 2110 MarkRoot</*kGrayImmuneObject*/true>(root); 2111 } 2112 } 2113 } 2114 2115 // Temporary set gc_grays_immune_objects_ to true in a scope if the current thread is GC. 2116 class ConcurrentCopying::ScopedGcGraysImmuneObjects { 2117 public: 2118 explicit ScopedGcGraysImmuneObjects(ConcurrentCopying* collector) 2119 : collector_(collector), enabled_(false) { 2120 if (kUseBakerReadBarrier && 2121 collector_->thread_running_gc_ == Thread::Current() && 2122 !collector_->gc_grays_immune_objects_) { 2123 collector_->gc_grays_immune_objects_ = true; 2124 enabled_ = true; 2125 } 2126 } 2127 2128 ~ScopedGcGraysImmuneObjects() { 2129 if (kUseBakerReadBarrier && 2130 collector_->thread_running_gc_ == Thread::Current() && 2131 enabled_) { 2132 DCHECK(collector_->gc_grays_immune_objects_); 2133 collector_->gc_grays_immune_objects_ = false; 2134 } 2135 } 2136 2137 private: 2138 ConcurrentCopying* const collector_; 2139 bool enabled_; 2140 }; 2141 2142 // Fill the given memory block with a dummy object. Used to fill in a 2143 // copy of objects that was lost in race. 2144 void ConcurrentCopying::FillWithDummyObject(mirror::Object* dummy_obj, size_t byte_size) { 2145 // GC doesn't gray immune objects while scanning immune objects. But we need to trigger the read 2146 // barriers here because we need the updated reference to the int array class, etc. Temporary set 2147 // gc_grays_immune_objects_ to true so that we won't cause a DCHECK failure in MarkImmuneSpace(). 2148 ScopedGcGraysImmuneObjects scoped_gc_gray_immune_objects(this); 2149 CHECK_ALIGNED(byte_size, kObjectAlignment); 2150 memset(dummy_obj, 0, byte_size); 2151 // Avoid going through read barrier for since kDisallowReadBarrierDuringScan may be enabled. 2152 // Explicitly mark to make sure to get an object in the to-space. 2153 mirror::Class* int_array_class = down_cast<mirror::Class*>( 2154 Mark(mirror::IntArray::GetArrayClass<kWithoutReadBarrier>())); 2155 CHECK(int_array_class != nullptr); 2156 AssertToSpaceInvariant(nullptr, MemberOffset(0), int_array_class); 2157 size_t component_size = int_array_class->GetComponentSize<kWithoutReadBarrier>(); 2158 CHECK_EQ(component_size, sizeof(int32_t)); 2159 size_t data_offset = mirror::Array::DataOffset(component_size).SizeValue(); 2160 if (data_offset > byte_size) { 2161 // An int array is too big. Use java.lang.Object. 2162 CHECK(java_lang_Object_ != nullptr); 2163 AssertToSpaceInvariant(nullptr, MemberOffset(0), java_lang_Object_); 2164 CHECK_EQ(byte_size, (java_lang_Object_->GetObjectSize<kVerifyNone, kWithoutReadBarrier>())); 2165 dummy_obj->SetClass(java_lang_Object_); 2166 CHECK_EQ(byte_size, (dummy_obj->SizeOf<kVerifyNone>())); 2167 } else { 2168 // Use an int array. 2169 dummy_obj->SetClass(int_array_class); 2170 CHECK((dummy_obj->IsArrayInstance<kVerifyNone, kWithoutReadBarrier>())); 2171 int32_t length = (byte_size - data_offset) / component_size; 2172 mirror::Array* dummy_arr = dummy_obj->AsArray<kVerifyNone, kWithoutReadBarrier>(); 2173 dummy_arr->SetLength(length); 2174 CHECK_EQ(dummy_arr->GetLength(), length) 2175 << "byte_size=" << byte_size << " length=" << length 2176 << " component_size=" << component_size << " data_offset=" << data_offset; 2177 CHECK_EQ(byte_size, (dummy_obj->SizeOf<kVerifyNone>())) 2178 << "byte_size=" << byte_size << " length=" << length 2179 << " component_size=" << component_size << " data_offset=" << data_offset; 2180 } 2181 } 2182 2183 // Reuse the memory blocks that were copy of objects that were lost in race. 2184 mirror::Object* ConcurrentCopying::AllocateInSkippedBlock(size_t alloc_size) { 2185 // Try to reuse the blocks that were unused due to CAS failures. 2186 CHECK_ALIGNED(alloc_size, space::RegionSpace::kAlignment); 2187 Thread* self = Thread::Current(); 2188 size_t min_object_size = RoundUp(sizeof(mirror::Object), space::RegionSpace::kAlignment); 2189 size_t byte_size; 2190 uint8_t* addr; 2191 { 2192 MutexLock mu(self, skipped_blocks_lock_); 2193 auto it = skipped_blocks_map_.lower_bound(alloc_size); 2194 if (it == skipped_blocks_map_.end()) { 2195 // Not found. 2196 return nullptr; 2197 } 2198 byte_size = it->first; 2199 CHECK_GE(byte_size, alloc_size); 2200 if (byte_size > alloc_size && byte_size - alloc_size < min_object_size) { 2201 // If remainder would be too small for a dummy object, retry with a larger request size. 2202 it = skipped_blocks_map_.lower_bound(alloc_size + min_object_size); 2203 if (it == skipped_blocks_map_.end()) { 2204 // Not found. 2205 return nullptr; 2206 } 2207 CHECK_ALIGNED(it->first - alloc_size, space::RegionSpace::kAlignment); 2208 CHECK_GE(it->first - alloc_size, min_object_size) 2209 << "byte_size=" << byte_size << " it->first=" << it->first << " alloc_size=" << alloc_size; 2210 } 2211 // Found a block. 2212 CHECK(it != skipped_blocks_map_.end()); 2213 byte_size = it->first; 2214 addr = it->second; 2215 CHECK_GE(byte_size, alloc_size); 2216 CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr))); 2217 CHECK_ALIGNED(byte_size, space::RegionSpace::kAlignment); 2218 if (kVerboseMode) { 2219 LOG(INFO) << "Reusing skipped bytes : " << reinterpret_cast<void*>(addr) << ", " << byte_size; 2220 } 2221 skipped_blocks_map_.erase(it); 2222 } 2223 memset(addr, 0, byte_size); 2224 if (byte_size > alloc_size) { 2225 // Return the remainder to the map. 2226 CHECK_ALIGNED(byte_size - alloc_size, space::RegionSpace::kAlignment); 2227 CHECK_GE(byte_size - alloc_size, min_object_size); 2228 // FillWithDummyObject may mark an object, avoid holding skipped_blocks_lock_ to prevent lock 2229 // violation and possible deadlock. The deadlock case is a recursive case: 2230 // FillWithDummyObject -> IntArray::GetArrayClass -> Mark -> Copy -> AllocateInSkippedBlock. 2231 FillWithDummyObject(reinterpret_cast<mirror::Object*>(addr + alloc_size), 2232 byte_size - alloc_size); 2233 CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr + alloc_size))); 2234 { 2235 MutexLock mu(self, skipped_blocks_lock_); 2236 skipped_blocks_map_.insert(std::make_pair(byte_size - alloc_size, addr + alloc_size)); 2237 } 2238 } 2239 return reinterpret_cast<mirror::Object*>(addr); 2240 } 2241 2242 mirror::Object* ConcurrentCopying::Copy(mirror::Object* from_ref, 2243 mirror::Object* holder, 2244 MemberOffset offset) { 2245 DCHECK(region_space_->IsInFromSpace(from_ref)); 2246 // If the class pointer is null, the object is invalid. This could occur for a dangling pointer 2247 // from a previous GC that is either inside or outside the allocated region. 2248 mirror::Class* klass = from_ref->GetClass<kVerifyNone, kWithoutReadBarrier>(); 2249 if (UNLIKELY(klass == nullptr)) { 2250 heap_->GetVerification()->LogHeapCorruption(holder, offset, from_ref, /* fatal */ true); 2251 } 2252 // There must not be a read barrier to avoid nested RB that might violate the to-space invariant. 2253 // Note that from_ref is a from space ref so the SizeOf() call will access the from-space meta 2254 // objects, but it's ok and necessary. 2255 size_t obj_size = from_ref->SizeOf<kDefaultVerifyFlags>(); 2256 size_t region_space_alloc_size = (obj_size <= space::RegionSpace::kRegionSize) 2257 ? RoundUp(obj_size, space::RegionSpace::kAlignment) 2258 : RoundUp(obj_size, space::RegionSpace::kRegionSize); 2259 size_t region_space_bytes_allocated = 0U; 2260 size_t non_moving_space_bytes_allocated = 0U; 2261 size_t bytes_allocated = 0U; 2262 size_t dummy; 2263 mirror::Object* to_ref = region_space_->AllocNonvirtual<true>( 2264 region_space_alloc_size, ®ion_space_bytes_allocated, nullptr, &dummy); 2265 bytes_allocated = region_space_bytes_allocated; 2266 if (to_ref != nullptr) { 2267 DCHECK_EQ(region_space_alloc_size, region_space_bytes_allocated); 2268 } 2269 bool fall_back_to_non_moving = false; 2270 if (UNLIKELY(to_ref == nullptr)) { 2271 // Failed to allocate in the region space. Try the skipped blocks. 2272 to_ref = AllocateInSkippedBlock(region_space_alloc_size); 2273 if (to_ref != nullptr) { 2274 // Succeeded to allocate in a skipped block. 2275 if (heap_->use_tlab_) { 2276 // This is necessary for the tlab case as it's not accounted in the space. 2277 region_space_->RecordAlloc(to_ref); 2278 } 2279 bytes_allocated = region_space_alloc_size; 2280 } else { 2281 // Fall back to the non-moving space. 2282 fall_back_to_non_moving = true; 2283 if (kVerboseMode) { 2284 LOG(INFO) << "Out of memory in the to-space. Fall back to non-moving. skipped_bytes=" 2285 << to_space_bytes_skipped_.LoadSequentiallyConsistent() 2286 << " skipped_objects=" << to_space_objects_skipped_.LoadSequentiallyConsistent(); 2287 } 2288 fall_back_to_non_moving = true; 2289 to_ref = heap_->non_moving_space_->Alloc(Thread::Current(), obj_size, 2290 &non_moving_space_bytes_allocated, nullptr, &dummy); 2291 if (UNLIKELY(to_ref == nullptr)) { 2292 LOG(FATAL_WITHOUT_ABORT) << "Fall-back non-moving space allocation failed for a " 2293 << obj_size << " byte object in region type " 2294 << region_space_->GetRegionType(from_ref); 2295 LOG(FATAL) << "Object address=" << from_ref << " type=" << from_ref->PrettyTypeOf(); 2296 } 2297 bytes_allocated = non_moving_space_bytes_allocated; 2298 // Mark it in the mark bitmap. 2299 accounting::ContinuousSpaceBitmap* mark_bitmap = 2300 heap_mark_bitmap_->GetContinuousSpaceBitmap(to_ref); 2301 CHECK(mark_bitmap != nullptr); 2302 CHECK(!mark_bitmap->AtomicTestAndSet(to_ref)); 2303 } 2304 } 2305 DCHECK(to_ref != nullptr); 2306 2307 // Copy the object excluding the lock word since that is handled in the loop. 2308 to_ref->SetClass(klass); 2309 const size_t kObjectHeaderSize = sizeof(mirror::Object); 2310 DCHECK_GE(obj_size, kObjectHeaderSize); 2311 static_assert(kObjectHeaderSize == sizeof(mirror::HeapReference<mirror::Class>) + 2312 sizeof(LockWord), 2313 "Object header size does not match"); 2314 // Memcpy can tear for words since it may do byte copy. It is only safe to do this since the 2315 // object in the from space is immutable other than the lock word. b/31423258 2316 memcpy(reinterpret_cast<uint8_t*>(to_ref) + kObjectHeaderSize, 2317 reinterpret_cast<const uint8_t*>(from_ref) + kObjectHeaderSize, 2318 obj_size - kObjectHeaderSize); 2319 2320 // Attempt to install the forward pointer. This is in a loop as the 2321 // lock word atomic write can fail. 2322 while (true) { 2323 LockWord old_lock_word = from_ref->GetLockWord(false); 2324 2325 if (old_lock_word.GetState() == LockWord::kForwardingAddress) { 2326 // Lost the race. Another thread (either GC or mutator) stored 2327 // the forwarding pointer first. Make the lost copy (to_ref) 2328 // look like a valid but dead (dummy) object and keep it for 2329 // future reuse. 2330 FillWithDummyObject(to_ref, bytes_allocated); 2331 if (!fall_back_to_non_moving) { 2332 DCHECK(region_space_->IsInToSpace(to_ref)); 2333 if (bytes_allocated > space::RegionSpace::kRegionSize) { 2334 // Free the large alloc. 2335 region_space_->FreeLarge(to_ref, bytes_allocated); 2336 } else { 2337 // Record the lost copy for later reuse. 2338 heap_->num_bytes_allocated_.FetchAndAddSequentiallyConsistent(bytes_allocated); 2339 to_space_bytes_skipped_.FetchAndAddSequentiallyConsistent(bytes_allocated); 2340 to_space_objects_skipped_.FetchAndAddSequentiallyConsistent(1); 2341 MutexLock mu(Thread::Current(), skipped_blocks_lock_); 2342 skipped_blocks_map_.insert(std::make_pair(bytes_allocated, 2343 reinterpret_cast<uint8_t*>(to_ref))); 2344 } 2345 } else { 2346 DCHECK(heap_->non_moving_space_->HasAddress(to_ref)); 2347 DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated); 2348 // Free the non-moving-space chunk. 2349 accounting::ContinuousSpaceBitmap* mark_bitmap = 2350 heap_mark_bitmap_->GetContinuousSpaceBitmap(to_ref); 2351 CHECK(mark_bitmap != nullptr); 2352 CHECK(mark_bitmap->Clear(to_ref)); 2353 heap_->non_moving_space_->Free(Thread::Current(), to_ref); 2354 } 2355 2356 // Get the winner's forward ptr. 2357 mirror::Object* lost_fwd_ptr = to_ref; 2358 to_ref = reinterpret_cast<mirror::Object*>(old_lock_word.ForwardingAddress()); 2359 CHECK(to_ref != nullptr); 2360 CHECK_NE(to_ref, lost_fwd_ptr); 2361 CHECK(region_space_->IsInToSpace(to_ref) || heap_->non_moving_space_->HasAddress(to_ref)) 2362 << "to_ref=" << to_ref << " " << heap_->DumpSpaces(); 2363 CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress); 2364 return to_ref; 2365 } 2366 2367 // Copy the old lock word over since we did not copy it yet. 2368 to_ref->SetLockWord(old_lock_word, false); 2369 // Set the gray ptr. 2370 if (kUseBakerReadBarrier) { 2371 to_ref->SetReadBarrierState(ReadBarrier::GrayState()); 2372 } 2373 2374 // Do a fence to prevent the field CAS in ConcurrentCopying::Process from possibly reordering 2375 // before the object copy. 2376 QuasiAtomic::ThreadFenceRelease(); 2377 2378 LockWord new_lock_word = LockWord::FromForwardingAddress(reinterpret_cast<size_t>(to_ref)); 2379 2380 // Try to atomically write the fwd ptr. 2381 bool success = from_ref->CasLockWordWeakRelaxed(old_lock_word, new_lock_word); 2382 if (LIKELY(success)) { 2383 // The CAS succeeded. 2384 objects_moved_.FetchAndAddRelaxed(1); 2385 bytes_moved_.FetchAndAddRelaxed(region_space_alloc_size); 2386 if (LIKELY(!fall_back_to_non_moving)) { 2387 DCHECK(region_space_->IsInToSpace(to_ref)); 2388 } else { 2389 DCHECK(heap_->non_moving_space_->HasAddress(to_ref)); 2390 DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated); 2391 } 2392 if (kUseBakerReadBarrier) { 2393 DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState()); 2394 } 2395 DCHECK(GetFwdPtr(from_ref) == to_ref); 2396 CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress); 2397 PushOntoMarkStack(to_ref); 2398 return to_ref; 2399 } else { 2400 // The CAS failed. It may have lost the race or may have failed 2401 // due to monitor/hashcode ops. Either way, retry. 2402 } 2403 } 2404 } 2405 2406 mirror::Object* ConcurrentCopying::IsMarked(mirror::Object* from_ref) { 2407 DCHECK(from_ref != nullptr); 2408 space::RegionSpace::RegionType rtype = region_space_->GetRegionType(from_ref); 2409 if (rtype == space::RegionSpace::RegionType::kRegionTypeToSpace) { 2410 // It's already marked. 2411 return from_ref; 2412 } 2413 mirror::Object* to_ref; 2414 if (rtype == space::RegionSpace::RegionType::kRegionTypeFromSpace) { 2415 to_ref = GetFwdPtr(from_ref); 2416 DCHECK(to_ref == nullptr || region_space_->IsInToSpace(to_ref) || 2417 heap_->non_moving_space_->HasAddress(to_ref)) 2418 << "from_ref=" << from_ref << " to_ref=" << to_ref; 2419 } else if (rtype == space::RegionSpace::RegionType::kRegionTypeUnevacFromSpace) { 2420 if (IsMarkedInUnevacFromSpace(from_ref)) { 2421 to_ref = from_ref; 2422 } else { 2423 to_ref = nullptr; 2424 } 2425 } else { 2426 // from_ref is in a non-moving space. 2427 if (immune_spaces_.ContainsObject(from_ref)) { 2428 // An immune object is alive. 2429 to_ref = from_ref; 2430 } else { 2431 // Non-immune non-moving space. Use the mark bitmap. 2432 accounting::ContinuousSpaceBitmap* mark_bitmap = 2433 heap_mark_bitmap_->GetContinuousSpaceBitmap(from_ref); 2434 bool is_los = mark_bitmap == nullptr; 2435 if (!is_los && mark_bitmap->Test(from_ref)) { 2436 // Already marked. 2437 to_ref = from_ref; 2438 } else { 2439 accounting::LargeObjectBitmap* los_bitmap = 2440 heap_mark_bitmap_->GetLargeObjectBitmap(from_ref); 2441 // We may not have a large object space for dex2oat, don't assume it exists. 2442 if (los_bitmap == nullptr) { 2443 CHECK(heap_->GetLargeObjectsSpace() == nullptr) 2444 << "LOS bitmap covers the entire address range " << from_ref 2445 << " " << heap_->DumpSpaces(); 2446 } 2447 if (los_bitmap != nullptr && is_los && los_bitmap->Test(from_ref)) { 2448 // Already marked in LOS. 2449 to_ref = from_ref; 2450 } else { 2451 // Not marked. 2452 if (IsOnAllocStack(from_ref)) { 2453 // If on the allocation stack, it's considered marked. 2454 to_ref = from_ref; 2455 } else { 2456 // Not marked. 2457 to_ref = nullptr; 2458 } 2459 } 2460 } 2461 } 2462 } 2463 return to_ref; 2464 } 2465 2466 bool ConcurrentCopying::IsOnAllocStack(mirror::Object* ref) { 2467 QuasiAtomic::ThreadFenceAcquire(); 2468 accounting::ObjectStack* alloc_stack = GetAllocationStack(); 2469 return alloc_stack->Contains(ref); 2470 } 2471 2472 mirror::Object* ConcurrentCopying::MarkNonMoving(mirror::Object* ref, 2473 mirror::Object* holder, 2474 MemberOffset offset) { 2475 // ref is in a non-moving space (from_ref == to_ref). 2476 DCHECK(!region_space_->HasAddress(ref)) << ref; 2477 DCHECK(!immune_spaces_.ContainsObject(ref)); 2478 // Use the mark bitmap. 2479 accounting::ContinuousSpaceBitmap* mark_bitmap = 2480 heap_mark_bitmap_->GetContinuousSpaceBitmap(ref); 2481 accounting::LargeObjectBitmap* los_bitmap = 2482 heap_mark_bitmap_->GetLargeObjectBitmap(ref); 2483 bool is_los = mark_bitmap == nullptr; 2484 if (!is_los && mark_bitmap->Test(ref)) { 2485 // Already marked. 2486 if (kUseBakerReadBarrier) { 2487 DCHECK(ref->GetReadBarrierState() == ReadBarrier::GrayState() || 2488 ref->GetReadBarrierState() == ReadBarrier::WhiteState()); 2489 } 2490 } else if (is_los && los_bitmap->Test(ref)) { 2491 // Already marked in LOS. 2492 if (kUseBakerReadBarrier) { 2493 DCHECK(ref->GetReadBarrierState() == ReadBarrier::GrayState() || 2494 ref->GetReadBarrierState() == ReadBarrier::WhiteState()); 2495 } 2496 } else { 2497 // Not marked. 2498 if (IsOnAllocStack(ref)) { 2499 // If it's on the allocation stack, it's considered marked. Keep it white. 2500 // Objects on the allocation stack need not be marked. 2501 if (!is_los) { 2502 DCHECK(!mark_bitmap->Test(ref)); 2503 } else { 2504 DCHECK(!los_bitmap->Test(ref)); 2505 } 2506 if (kUseBakerReadBarrier) { 2507 DCHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::WhiteState()); 2508 } 2509 } else { 2510 // For the baker-style RB, we need to handle 'false-gray' cases. See the 2511 // kRegionTypeUnevacFromSpace-case comment in Mark(). 2512 if (kUseBakerReadBarrier) { 2513 // Test the bitmap first to reduce the chance of false gray cases. 2514 if ((!is_los && mark_bitmap->Test(ref)) || 2515 (is_los && los_bitmap->Test(ref))) { 2516 return ref; 2517 } 2518 } 2519 if (is_los && !IsAligned<kPageSize>(ref)) { 2520 // Ref is a large object that is not aligned, it must be heap corruption. Dump data before 2521 // AtomicSetReadBarrierState since it will fault if the address is not valid. 2522 heap_->GetVerification()->LogHeapCorruption(holder, offset, ref, /* fatal */ true); 2523 } 2524 // Not marked or on the allocation stack. Try to mark it. 2525 // This may or may not succeed, which is ok. 2526 bool cas_success = false; 2527 if (kUseBakerReadBarrier) { 2528 cas_success = ref->AtomicSetReadBarrierState(ReadBarrier::WhiteState(), 2529 ReadBarrier::GrayState()); 2530 } 2531 if (!is_los && mark_bitmap->AtomicTestAndSet(ref)) { 2532 // Already marked. 2533 if (kUseBakerReadBarrier && cas_success && 2534 ref->GetReadBarrierState() == ReadBarrier::GrayState()) { 2535 PushOntoFalseGrayStack(ref); 2536 } 2537 } else if (is_los && los_bitmap->AtomicTestAndSet(ref)) { 2538 // Already marked in LOS. 2539 if (kUseBakerReadBarrier && cas_success && 2540 ref->GetReadBarrierState() == ReadBarrier::GrayState()) { 2541 PushOntoFalseGrayStack(ref); 2542 } 2543 } else { 2544 // Newly marked. 2545 if (kUseBakerReadBarrier) { 2546 DCHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::GrayState()); 2547 } 2548 PushOntoMarkStack(ref); 2549 } 2550 } 2551 } 2552 return ref; 2553 } 2554 2555 void ConcurrentCopying::FinishPhase() { 2556 Thread* const self = Thread::Current(); 2557 { 2558 MutexLock mu(self, mark_stack_lock_); 2559 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize); 2560 } 2561 // kVerifyNoMissingCardMarks relies on the region space cards not being cleared to avoid false 2562 // positives. 2563 if (!kVerifyNoMissingCardMarks) { 2564 TimingLogger::ScopedTiming split("ClearRegionSpaceCards", GetTimings()); 2565 // We do not currently use the region space cards at all, madvise them away to save ram. 2566 heap_->GetCardTable()->ClearCardRange(region_space_->Begin(), region_space_->Limit()); 2567 } 2568 { 2569 MutexLock mu(self, skipped_blocks_lock_); 2570 skipped_blocks_map_.clear(); 2571 } 2572 { 2573 ReaderMutexLock mu(self, *Locks::mutator_lock_); 2574 { 2575 WriterMutexLock mu2(self, *Locks::heap_bitmap_lock_); 2576 heap_->ClearMarkedObjects(); 2577 } 2578 if (kUseBakerReadBarrier && kFilterModUnionCards) { 2579 TimingLogger::ScopedTiming split("FilterModUnionCards", GetTimings()); 2580 ReaderMutexLock mu2(self, *Locks::heap_bitmap_lock_); 2581 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) { 2582 DCHECK(space->IsImageSpace() || space->IsZygoteSpace()); 2583 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); 2584 // Filter out cards that don't need to be set. 2585 if (table != nullptr) { 2586 table->FilterCards(); 2587 } 2588 } 2589 } 2590 if (kUseBakerReadBarrier) { 2591 TimingLogger::ScopedTiming split("EmptyRBMarkBitStack", GetTimings()); 2592 DCHECK(rb_mark_bit_stack_ != nullptr); 2593 const auto* limit = rb_mark_bit_stack_->End(); 2594 for (StackReference<mirror::Object>* it = rb_mark_bit_stack_->Begin(); it != limit; ++it) { 2595 CHECK(it->AsMirrorPtr()->AtomicSetMarkBit(1, 0)); 2596 } 2597 rb_mark_bit_stack_->Reset(); 2598 } 2599 } 2600 if (measure_read_barrier_slow_path_) { 2601 MutexLock mu(self, rb_slow_path_histogram_lock_); 2602 rb_slow_path_time_histogram_.AdjustAndAddValue(rb_slow_path_ns_.LoadRelaxed()); 2603 rb_slow_path_count_total_ += rb_slow_path_count_.LoadRelaxed(); 2604 rb_slow_path_count_gc_total_ += rb_slow_path_count_gc_.LoadRelaxed(); 2605 } 2606 } 2607 2608 bool ConcurrentCopying::IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object>* field, 2609 bool do_atomic_update) { 2610 mirror::Object* from_ref = field->AsMirrorPtr(); 2611 if (from_ref == nullptr) { 2612 return true; 2613 } 2614 mirror::Object* to_ref = IsMarked(from_ref); 2615 if (to_ref == nullptr) { 2616 return false; 2617 } 2618 if (from_ref != to_ref) { 2619 if (do_atomic_update) { 2620 do { 2621 if (field->AsMirrorPtr() != from_ref) { 2622 // Concurrently overwritten by a mutator. 2623 break; 2624 } 2625 } while (!field->CasWeakRelaxed(from_ref, to_ref)); 2626 } else { 2627 QuasiAtomic::ThreadFenceRelease(); 2628 field->Assign(to_ref); 2629 QuasiAtomic::ThreadFenceSequentiallyConsistent(); 2630 } 2631 } 2632 return true; 2633 } 2634 2635 mirror::Object* ConcurrentCopying::MarkObject(mirror::Object* from_ref) { 2636 return Mark(from_ref); 2637 } 2638 2639 void ConcurrentCopying::DelayReferenceReferent(ObjPtr<mirror::Class> klass, 2640 ObjPtr<mirror::Reference> reference) { 2641 heap_->GetReferenceProcessor()->DelayReferenceReferent(klass, reference, this); 2642 } 2643 2644 void ConcurrentCopying::ProcessReferences(Thread* self) { 2645 TimingLogger::ScopedTiming split("ProcessReferences", GetTimings()); 2646 // We don't really need to lock the heap bitmap lock as we use CAS to mark in bitmaps. 2647 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 2648 GetHeap()->GetReferenceProcessor()->ProcessReferences( 2649 true /*concurrent*/, GetTimings(), GetCurrentIteration()->GetClearSoftReferences(), this); 2650 } 2651 2652 void ConcurrentCopying::RevokeAllThreadLocalBuffers() { 2653 TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings()); 2654 region_space_->RevokeAllThreadLocalBuffers(); 2655 } 2656 2657 mirror::Object* ConcurrentCopying::MarkFromReadBarrierWithMeasurements(mirror::Object* from_ref) { 2658 if (Thread::Current() != thread_running_gc_) { 2659 rb_slow_path_count_.FetchAndAddRelaxed(1u); 2660 } else { 2661 rb_slow_path_count_gc_.FetchAndAddRelaxed(1u); 2662 } 2663 ScopedTrace tr(__FUNCTION__); 2664 const uint64_t start_time = measure_read_barrier_slow_path_ ? NanoTime() : 0u; 2665 mirror::Object* ret = Mark(from_ref); 2666 if (measure_read_barrier_slow_path_) { 2667 rb_slow_path_ns_.FetchAndAddRelaxed(NanoTime() - start_time); 2668 } 2669 return ret; 2670 } 2671 2672 void ConcurrentCopying::DumpPerformanceInfo(std::ostream& os) { 2673 GarbageCollector::DumpPerformanceInfo(os); 2674 MutexLock mu(Thread::Current(), rb_slow_path_histogram_lock_); 2675 if (rb_slow_path_time_histogram_.SampleSize() > 0) { 2676 Histogram<uint64_t>::CumulativeData cumulative_data; 2677 rb_slow_path_time_histogram_.CreateHistogram(&cumulative_data); 2678 rb_slow_path_time_histogram_.PrintConfidenceIntervals(os, 0.99, cumulative_data); 2679 } 2680 if (rb_slow_path_count_total_ > 0) { 2681 os << "Slow path count " << rb_slow_path_count_total_ << "\n"; 2682 } 2683 if (rb_slow_path_count_gc_total_ > 0) { 2684 os << "GC slow path count " << rb_slow_path_count_gc_total_ << "\n"; 2685 } 2686 os << "Cumulative bytes moved " << cumulative_bytes_moved_.LoadRelaxed() << "\n"; 2687 os << "Cumulative objects moved " << cumulative_objects_moved_.LoadRelaxed() << "\n"; 2688 } 2689 2690 } // namespace collector 2691 } // namespace gc 2692 } // namespace art 2693