mark_sweep.cc revision cf58d4adf461eb9b8e84baa8019054c88cd8acc6
1/* 2 * Copyright (C) 2011 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 "mark_sweep.h" 18 19#include <functional> 20#include <numeric> 21#include <climits> 22#include <vector> 23 24#include "base/bounded_fifo.h" 25#include "base/logging.h" 26#include "base/macros.h" 27#include "base/mutex-inl.h" 28#include "base/timing_logger.h" 29#include "gc/accounting/card_table-inl.h" 30#include "gc/accounting/heap_bitmap.h" 31#include "gc/accounting/mod_union_table.h" 32#include "gc/accounting/space_bitmap-inl.h" 33#include "gc/heap.h" 34#include "gc/space/image_space.h" 35#include "gc/space/large_object_space.h" 36#include "gc/space/space-inl.h" 37#include "indirect_reference_table.h" 38#include "intern_table.h" 39#include "jni_internal.h" 40#include "monitor.h" 41#include "mark_sweep-inl.h" 42#include "mirror/art_field.h" 43#include "mirror/art_field-inl.h" 44#include "mirror/class-inl.h" 45#include "mirror/class_loader.h" 46#include "mirror/dex_cache.h" 47#include "mirror/object-inl.h" 48#include "mirror/object_array.h" 49#include "mirror/object_array-inl.h" 50#include "runtime.h" 51#include "thread-inl.h" 52#include "thread_list.h" 53#include "verifier/method_verifier.h" 54 55using ::art::mirror::ArtField; 56using ::art::mirror::Class; 57using ::art::mirror::Object; 58using ::art::mirror::ObjectArray; 59 60namespace art { 61namespace gc { 62namespace collector { 63 64// Performance options. 65constexpr bool kUseRecursiveMark = false; 66constexpr bool kUseMarkStackPrefetch = true; 67constexpr size_t kSweepArrayChunkFreeSize = 1024; 68 69// Parallelism options. 70constexpr bool kParallelCardScan = true; 71constexpr bool kParallelRecursiveMark = true; 72// Don't attempt to parallelize mark stack processing unless the mark stack is at least n 73// elements. This is temporary until we reduce the overhead caused by allocating tasks, etc.. Not 74// having this can add overhead in ProcessReferences since we may end up doing many calls of 75// ProcessMarkStack with very small mark stacks. 76constexpr size_t kMinimumParallelMarkStackSize = 128; 77constexpr bool kParallelProcessMarkStack = true; 78 79// Profiling and information flags. 80constexpr bool kCountClassesMarked = false; 81constexpr bool kProfileLargeObjects = false; 82constexpr bool kMeasureOverhead = false; 83constexpr bool kCountTasks = false; 84constexpr bool kCountJavaLangRefs = false; 85 86// Turn off kCheckLocks when profiling the GC since it slows the GC down by up to 40%. 87constexpr bool kCheckLocks = kDebugLocking; 88 89void MarkSweep::ImmuneSpace(space::ContinuousSpace* space) { 90 // Bind live to mark bitmap if necessary. 91 if (space->GetLiveBitmap() != space->GetMarkBitmap()) { 92 BindLiveToMarkBitmap(space); 93 } 94 95 // Add the space to the immune region. 96 // TODO: Use space limits instead of current end_ since the end_ can be changed by dlmalloc 97 // callbacks. 98 if (immune_begin_ == NULL) { 99 DCHECK(immune_end_ == NULL); 100 SetImmuneRange(reinterpret_cast<Object*>(space->Begin()), 101 reinterpret_cast<Object*>(space->End())); 102 } else { 103 const space::ContinuousSpace* prev_space = nullptr; 104 // Find out if the previous space is immune. 105 for (const space::ContinuousSpace* cur_space : GetHeap()->GetContinuousSpaces()) { 106 if (cur_space == space) { 107 break; 108 } 109 prev_space = cur_space; 110 } 111 // If previous space was immune, then extend the immune region. Relies on continuous spaces 112 // being sorted by Heap::AddContinuousSpace. 113 if (prev_space != nullptr && IsImmuneSpace(prev_space)) { 114 immune_begin_ = std::min(reinterpret_cast<Object*>(space->Begin()), immune_begin_); 115 immune_end_ = std::max(reinterpret_cast<Object*>(space->End()), immune_end_); 116 } 117 } 118} 119 120bool MarkSweep::IsImmuneSpace(const space::ContinuousSpace* space) const { 121 return 122 immune_begin_ <= reinterpret_cast<Object*>(space->Begin()) && 123 immune_end_ >= reinterpret_cast<Object*>(space->End()); 124} 125 126void MarkSweep::BindBitmaps() { 127 timings_.StartSplit("BindBitmaps"); 128 WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_); 129 // Mark all of the spaces we never collect as immune. 130 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 131 if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect) { 132 ImmuneSpace(space); 133 } 134 } 135 timings_.EndSplit(); 136} 137 138MarkSweep::MarkSweep(Heap* heap, bool is_concurrent, const std::string& name_prefix) 139 : GarbageCollector(heap, 140 name_prefix + 141 (is_concurrent ? "concurrent mark sweep": "mark sweep")), 142 current_mark_bitmap_(NULL), 143 mark_stack_(NULL), 144 immune_begin_(NULL), 145 immune_end_(NULL), 146 soft_reference_list_(NULL), 147 weak_reference_list_(NULL), 148 finalizer_reference_list_(NULL), 149 phantom_reference_list_(NULL), 150 cleared_reference_list_(NULL), 151 live_stack_freeze_size_(0), 152 gc_barrier_(new Barrier(0)), 153 large_object_lock_("mark sweep large object lock", kMarkSweepLargeObjectLock), 154 mark_stack_lock_("mark sweep mark stack lock", kMarkSweepMarkStackLock), 155 is_concurrent_(is_concurrent) { 156} 157 158void MarkSweep::InitializePhase() { 159 timings_.Reset(); 160 TimingLogger::ScopedSplit split("InitializePhase", &timings_); 161 mark_stack_ = heap_->mark_stack_.get(); 162 DCHECK(mark_stack_ != nullptr); 163 SetImmuneRange(nullptr, nullptr); 164 soft_reference_list_ = nullptr; 165 weak_reference_list_ = nullptr; 166 finalizer_reference_list_ = nullptr; 167 phantom_reference_list_ = nullptr; 168 cleared_reference_list_ = nullptr; 169 class_count_ = 0; 170 array_count_ = 0; 171 other_count_ = 0; 172 large_object_test_ = 0; 173 large_object_mark_ = 0; 174 classes_marked_ = 0; 175 overhead_time_ = 0; 176 work_chunks_created_ = 0; 177 work_chunks_deleted_ = 0; 178 reference_count_ = 0; 179 180 FindDefaultMarkBitmap(); 181 182 // Do any pre GC verification. 183 timings_.NewSplit("PreGcVerification"); 184 heap_->PreGcVerification(this); 185} 186 187void MarkSweep::ProcessReferences(Thread* self) { 188 TimingLogger::ScopedSplit split("ProcessReferences", &timings_); 189 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 190 GetHeap()->ProcessReferences(timings_, clear_soft_references_, &IsMarkedCallback, 191 &RecursiveMarkObjectCallback, this); 192} 193 194bool MarkSweep::HandleDirtyObjectsPhase() { 195 TimingLogger::ScopedSplit split("HandleDirtyObjectsPhase", &timings_); 196 Thread* self = Thread::Current(); 197 Locks::mutator_lock_->AssertExclusiveHeld(self); 198 199 { 200 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 201 202 // Re-mark root set. 203 ReMarkRoots(); 204 205 // Scan dirty objects, this is only required if we are not doing concurrent GC. 206 RecursiveMarkDirtyObjects(true, accounting::CardTable::kCardDirty); 207 } 208 209 ProcessReferences(self); 210 211 // Only need to do this if we have the card mark verification on, and only during concurrent GC. 212 if (GetHeap()->verify_missing_card_marks_ || GetHeap()->verify_pre_gc_heap_|| 213 GetHeap()->verify_post_gc_heap_) { 214 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 215 // This second sweep makes sure that we don't have any objects in the live stack which point to 216 // freed objects. These cause problems since their references may be previously freed objects. 217 SweepArray(GetHeap()->allocation_stack_.get(), false); 218 } 219 220 timings_.StartSplit("PreSweepingGcVerification"); 221 heap_->PreSweepingGcVerification(this); 222 timings_.EndSplit(); 223 224 // Ensure that nobody inserted items in the live stack after we swapped the stacks. 225 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 226 CHECK_GE(live_stack_freeze_size_, GetHeap()->GetLiveStack()->Size()); 227 228 // Disallow new system weaks to prevent a race which occurs when someone adds a new system 229 // weak before we sweep them. Since this new system weak may not be marked, the GC may 230 // incorrectly sweep it. This also fixes a race where interning may attempt to return a strong 231 // reference to a string that is about to be swept. 232 Runtime::Current()->DisallowNewSystemWeaks(); 233 return true; 234} 235 236bool MarkSweep::IsConcurrent() const { 237 return is_concurrent_; 238} 239 240void MarkSweep::MarkingPhase() { 241 TimingLogger::ScopedSplit split("MarkingPhase", &timings_); 242 Thread* self = Thread::Current(); 243 244 BindBitmaps(); 245 FindDefaultMarkBitmap(); 246 247 // Process dirty cards and add dirty cards to mod union tables. 248 heap_->ProcessCards(timings_); 249 250 // Need to do this before the checkpoint since we don't want any threads to add references to 251 // the live stack during the recursive mark. 252 timings_.NewSplit("SwapStacks"); 253 heap_->SwapStacks(); 254 255 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 256 if (Locks::mutator_lock_->IsExclusiveHeld(self)) { 257 // If we exclusively hold the mutator lock, all threads must be suspended. 258 MarkRoots(); 259 } else { 260 MarkThreadRoots(self); 261 // At this point the live stack should no longer have any mutators which push into it. 262 MarkNonThreadRoots(); 263 } 264 live_stack_freeze_size_ = heap_->GetLiveStack()->Size(); 265 MarkConcurrentRoots(); 266 UpdateAndMarkModUnion(); 267 MarkReachableObjects(); 268} 269 270void MarkSweep::UpdateAndMarkModUnion() { 271 for (const auto& space : heap_->GetContinuousSpaces()) { 272 if (IsImmuneSpace(space)) { 273 const char* name = space->IsZygoteSpace() ? "UpdateAndMarkZygoteModUnionTable" : 274 "UpdateAndMarkImageModUnionTable"; 275 TimingLogger::ScopedSplit split(name, &timings_); 276 accounting::ModUnionTable* mod_union_table = heap_->FindModUnionTableFromSpace(space); 277 CHECK(mod_union_table != nullptr); 278 mod_union_table->UpdateAndMarkReferences(MarkRootCallback, this); 279 } 280 } 281} 282 283void MarkSweep::MarkThreadRoots(Thread* self) { 284 MarkRootsCheckpoint(self); 285} 286 287void MarkSweep::MarkReachableObjects() { 288 // Mark everything allocated since the last as GC live so that we can sweep concurrently, 289 // knowing that new allocations won't be marked as live. 290 timings_.StartSplit("MarkStackAsLive"); 291 accounting::ObjectStack* live_stack = heap_->GetLiveStack(); 292 heap_->MarkAllocStackAsLive(live_stack); 293 live_stack->Reset(); 294 timings_.EndSplit(); 295 // Recursively mark all the non-image bits set in the mark bitmap. 296 RecursiveMark(); 297} 298 299void MarkSweep::ReclaimPhase() { 300 TimingLogger::ScopedSplit split("ReclaimPhase", &timings_); 301 Thread* self = Thread::Current(); 302 303 if (!IsConcurrent()) { 304 ProcessReferences(self); 305 } 306 307 { 308 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 309 SweepSystemWeaks(); 310 } 311 312 if (IsConcurrent()) { 313 Runtime::Current()->AllowNewSystemWeaks(); 314 315 TimingLogger::ScopedSplit split("UnMarkAllocStack", &timings_); 316 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 317 accounting::ObjectStack* allocation_stack = GetHeap()->allocation_stack_.get(); 318 // The allocation stack contains things allocated since the start of the GC. These may have been 319 // marked during this GC meaning they won't be eligible for reclaiming in the next sticky GC. 320 // Remove these objects from the mark bitmaps so that they will be eligible for sticky 321 // collection. 322 // There is a race here which is safely handled. Another thread such as the hprof could 323 // have flushed the alloc stack after we resumed the threads. This is safe however, since 324 // reseting the allocation stack zeros it out with madvise. This means that we will either 325 // read NULLs or attempt to unmark a newly allocated object which will not be marked in the 326 // first place. 327 mirror::Object** end = allocation_stack->End(); 328 for (mirror::Object** it = allocation_stack->Begin(); it != end; ++it) { 329 const Object* obj = *it; 330 if (obj != NULL) { 331 UnMarkObjectNonNull(obj); 332 } 333 } 334 } 335 336 // Before freeing anything, lets verify the heap. 337 if (kIsDebugBuild) { 338 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 339 VerifyImageRoots(); 340 } 341 342 { 343 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 344 345 // Reclaim unmarked objects. 346 Sweep(false); 347 348 // Swap the live and mark bitmaps for each space which we modified space. This is an 349 // optimization that enables us to not clear live bits inside of the sweep. Only swaps unbound 350 // bitmaps. 351 timings_.StartSplit("SwapBitmaps"); 352 SwapBitmaps(); 353 timings_.EndSplit(); 354 355 // Unbind the live and mark bitmaps. 356 UnBindBitmaps(); 357 } 358} 359 360void MarkSweep::SetImmuneRange(Object* begin, Object* end) { 361 immune_begin_ = begin; 362 immune_end_ = end; 363} 364 365void MarkSweep::FindDefaultMarkBitmap() { 366 TimingLogger::ScopedSplit split("FindDefaultMarkBitmap", &timings_); 367 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 368 accounting::SpaceBitmap* bitmap = space->GetMarkBitmap(); 369 if (bitmap != nullptr && 370 space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) { 371 current_mark_bitmap_ = bitmap; 372 CHECK(current_mark_bitmap_ != NULL); 373 return; 374 } 375 } 376 GetHeap()->DumpSpaces(); 377 LOG(FATAL) << "Could not find a default mark bitmap"; 378} 379 380void MarkSweep::ExpandMarkStack() { 381 ResizeMarkStack(mark_stack_->Capacity() * 2); 382} 383 384void MarkSweep::ResizeMarkStack(size_t new_size) { 385 // Rare case, no need to have Thread::Current be a parameter. 386 if (UNLIKELY(mark_stack_->Size() < mark_stack_->Capacity())) { 387 // Someone else acquired the lock and expanded the mark stack before us. 388 return; 389 } 390 std::vector<Object*> temp(mark_stack_->Begin(), mark_stack_->End()); 391 CHECK_LE(mark_stack_->Size(), new_size); 392 mark_stack_->Resize(new_size); 393 for (const auto& obj : temp) { 394 mark_stack_->PushBack(obj); 395 } 396} 397 398inline void MarkSweep::MarkObjectNonNullParallel(const Object* obj) { 399 DCHECK(obj != NULL); 400 if (MarkObjectParallel(obj)) { 401 MutexLock mu(Thread::Current(), mark_stack_lock_); 402 if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 403 ExpandMarkStack(); 404 } 405 // The object must be pushed on to the mark stack. 406 mark_stack_->PushBack(const_cast<Object*>(obj)); 407 } 408} 409 410mirror::Object* MarkSweep::RecursiveMarkObjectCallback(mirror::Object* obj, void* arg) { 411 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 412 mark_sweep->MarkObject(obj); 413 mark_sweep->ProcessMarkStack(true); 414 return obj; 415} 416 417inline void MarkSweep::UnMarkObjectNonNull(const Object* obj) { 418 DCHECK(!IsImmune(obj)); 419 // Try to take advantage of locality of references within a space, failing this find the space 420 // the hard way. 421 accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 422 if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 423 accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 424 if (LIKELY(new_bitmap != NULL)) { 425 object_bitmap = new_bitmap; 426 } else { 427 MarkLargeObject(obj, false); 428 return; 429 } 430 } 431 432 DCHECK(object_bitmap->HasAddress(obj)); 433 object_bitmap->Clear(obj); 434} 435 436inline void MarkSweep::MarkObjectNonNull(const Object* obj) { 437 DCHECK(obj != NULL); 438 439 if (IsImmune(obj)) { 440 DCHECK(IsMarked(obj)); 441 return; 442 } 443 444 // Try to take advantage of locality of references within a space, failing this find the space 445 // the hard way. 446 accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 447 if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 448 accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 449 if (LIKELY(new_bitmap != NULL)) { 450 object_bitmap = new_bitmap; 451 } else { 452 MarkLargeObject(obj, true); 453 return; 454 } 455 } 456 457 // This object was not previously marked. 458 if (!object_bitmap->Test(obj)) { 459 object_bitmap->Set(obj); 460 if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 461 // Lock is not needed but is here anyways to please annotalysis. 462 MutexLock mu(Thread::Current(), mark_stack_lock_); 463 ExpandMarkStack(); 464 } 465 // The object must be pushed on to the mark stack. 466 mark_stack_->PushBack(const_cast<Object*>(obj)); 467 } 468} 469 470// Rare case, probably not worth inlining since it will increase instruction cache miss rate. 471bool MarkSweep::MarkLargeObject(const Object* obj, bool set) { 472 // TODO: support >1 discontinuous space. 473 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 474 accounting::SpaceSetMap* large_objects = large_object_space->GetMarkObjects(); 475 if (kProfileLargeObjects) { 476 ++large_object_test_; 477 } 478 if (UNLIKELY(!large_objects->Test(obj))) { 479 if (!large_object_space->Contains(obj)) { 480 LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces"; 481 LOG(ERROR) << "Attempting see if it's a bad root"; 482 VerifyRoots(); 483 LOG(FATAL) << "Can't mark bad root"; 484 } 485 if (kProfileLargeObjects) { 486 ++large_object_mark_; 487 } 488 if (set) { 489 large_objects->Set(obj); 490 } else { 491 large_objects->Clear(obj); 492 } 493 return true; 494 } 495 return false; 496} 497 498inline bool MarkSweep::MarkObjectParallel(const Object* obj) { 499 DCHECK(obj != NULL); 500 501 if (IsImmune(obj)) { 502 DCHECK(IsMarked(obj)); 503 return false; 504 } 505 506 // Try to take advantage of locality of references within a space, failing this find the space 507 // the hard way. 508 accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 509 if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 510 accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 511 if (new_bitmap != NULL) { 512 object_bitmap = new_bitmap; 513 } else { 514 // TODO: Remove the Thread::Current here? 515 // TODO: Convert this to some kind of atomic marking? 516 MutexLock mu(Thread::Current(), large_object_lock_); 517 return MarkLargeObject(obj, true); 518 } 519 } 520 521 // Return true if the object was not previously marked. 522 return !object_bitmap->AtomicTestAndSet(obj); 523} 524 525// Used to mark objects when recursing. Recursion is done by moving 526// the finger across the bitmaps in address order and marking child 527// objects. Any newly-marked objects whose addresses are lower than 528// the finger won't be visited by the bitmap scan, so those objects 529// need to be added to the mark stack. 530inline void MarkSweep::MarkObject(const Object* obj) { 531 if (obj != NULL) { 532 MarkObjectNonNull(obj); 533 } 534} 535 536void MarkSweep::MarkRoot(const Object* obj) { 537 if (obj != NULL) { 538 MarkObjectNonNull(obj); 539 } 540} 541 542Object* MarkSweep::MarkRootParallelCallback(Object* root, void* arg) { 543 DCHECK(root != NULL); 544 DCHECK(arg != NULL); 545 reinterpret_cast<MarkSweep*>(arg)->MarkObjectNonNullParallel(root); 546 return root; 547} 548 549Object* MarkSweep::MarkRootCallback(Object* root, void* arg) { 550 DCHECK(root != nullptr); 551 DCHECK(arg != nullptr); 552 reinterpret_cast<MarkSweep*>(arg)->MarkObjectNonNull(root); 553 return root; 554} 555 556void MarkSweep::VerifyRootCallback(const Object* root, void* arg, size_t vreg, 557 const StackVisitor* visitor) { 558 reinterpret_cast<MarkSweep*>(arg)->VerifyRoot(root, vreg, visitor); 559} 560 561void MarkSweep::VerifyRoot(const Object* root, size_t vreg, const StackVisitor* visitor) { 562 // See if the root is on any space bitmap. 563 if (GetHeap()->GetLiveBitmap()->GetContinuousSpaceBitmap(root) == NULL) { 564 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 565 if (!large_object_space->Contains(root)) { 566 LOG(ERROR) << "Found invalid root: " << root; 567 if (visitor != NULL) { 568 LOG(ERROR) << visitor->DescribeLocation() << " in VReg: " << vreg; 569 } 570 } 571 } 572} 573 574void MarkSweep::VerifyRoots() { 575 Runtime::Current()->GetThreadList()->VerifyRoots(VerifyRootCallback, this); 576} 577 578// Marks all objects in the root set. 579void MarkSweep::MarkRoots() { 580 timings_.StartSplit("MarkRoots"); 581 Runtime::Current()->VisitNonConcurrentRoots(MarkRootCallback, this); 582 timings_.EndSplit(); 583} 584 585void MarkSweep::MarkNonThreadRoots() { 586 timings_.StartSplit("MarkNonThreadRoots"); 587 Runtime::Current()->VisitNonThreadRoots(MarkRootCallback, this); 588 timings_.EndSplit(); 589} 590 591void MarkSweep::MarkConcurrentRoots() { 592 timings_.StartSplit("MarkConcurrentRoots"); 593 // Visit all runtime roots and clear dirty flags. 594 Runtime::Current()->VisitConcurrentRoots(MarkRootCallback, this, false, true); 595 timings_.EndSplit(); 596} 597 598void MarkSweep::CheckObject(const Object* obj) { 599 DCHECK(obj != NULL); 600 VisitObjectReferences(const_cast<Object*>(obj), [this](const Object* obj, const Object* ref, 601 MemberOffset offset, bool is_static) NO_THREAD_SAFETY_ANALYSIS { 602 Locks::heap_bitmap_lock_->AssertSharedHeld(Thread::Current()); 603 CheckReference(obj, ref, offset, is_static); 604 }, true); 605} 606 607void MarkSweep::VerifyImageRootVisitor(Object* root, void* arg) { 608 DCHECK(root != NULL); 609 DCHECK(arg != NULL); 610 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 611 DCHECK(mark_sweep->heap_->GetMarkBitmap()->Test(root)); 612 mark_sweep->CheckObject(root); 613} 614 615void MarkSweep::BindLiveToMarkBitmap(space::ContinuousSpace* space) { 616 CHECK(space->IsMallocSpace()); 617 space::MallocSpace* alloc_space = space->AsMallocSpace(); 618 accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 619 accounting::SpaceBitmap* mark_bitmap = alloc_space->BindLiveToMarkBitmap(); 620 GetHeap()->GetMarkBitmap()->ReplaceBitmap(mark_bitmap, live_bitmap); 621} 622 623class ScanObjectVisitor { 624 public: 625 explicit ScanObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE 626 : mark_sweep_(mark_sweep) {} 627 628 // TODO: Fixme when anotatalysis works with visitors. 629 void operator()(Object* obj) const ALWAYS_INLINE NO_THREAD_SAFETY_ANALYSIS { 630 if (kCheckLocks) { 631 Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 632 Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 633 } 634 mark_sweep_->ScanObject(obj); 635 } 636 637 private: 638 MarkSweep* const mark_sweep_; 639}; 640 641template <bool kUseFinger = false> 642class MarkStackTask : public Task { 643 public: 644 MarkStackTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, size_t mark_stack_size, 645 const Object** mark_stack) 646 : mark_sweep_(mark_sweep), 647 thread_pool_(thread_pool), 648 mark_stack_pos_(mark_stack_size) { 649 // We may have to copy part of an existing mark stack when another mark stack overflows. 650 if (mark_stack_size != 0) { 651 DCHECK(mark_stack != NULL); 652 // TODO: Check performance? 653 std::copy(mark_stack, mark_stack + mark_stack_size, mark_stack_); 654 } 655 if (kCountTasks) { 656 ++mark_sweep_->work_chunks_created_; 657 } 658 } 659 660 static const size_t kMaxSize = 1 * KB; 661 662 protected: 663 class ScanObjectParallelVisitor { 664 public: 665 explicit ScanObjectParallelVisitor(MarkStackTask<kUseFinger>* chunk_task) ALWAYS_INLINE 666 : chunk_task_(chunk_task) {} 667 668 void operator()(Object* obj) const { 669 MarkSweep* mark_sweep = chunk_task_->mark_sweep_; 670 mark_sweep->ScanObjectVisit(obj, 671 [mark_sweep, this](Object* /* obj */, Object* ref, const MemberOffset& /* offset */, 672 bool /* is_static */) ALWAYS_INLINE { 673 if (ref != nullptr && mark_sweep->MarkObjectParallel(ref)) { 674 if (kUseFinger) { 675 android_memory_barrier(); 676 if (reinterpret_cast<uintptr_t>(ref) >= 677 static_cast<uintptr_t>(mark_sweep->atomic_finger_)) { 678 return; 679 } 680 } 681 chunk_task_->MarkStackPush(ref); 682 } 683 }); 684 } 685 686 private: 687 MarkStackTask<kUseFinger>* const chunk_task_; 688 }; 689 690 virtual ~MarkStackTask() { 691 // Make sure that we have cleared our mark stack. 692 DCHECK_EQ(mark_stack_pos_, 0U); 693 if (kCountTasks) { 694 ++mark_sweep_->work_chunks_deleted_; 695 } 696 } 697 698 MarkSweep* const mark_sweep_; 699 ThreadPool* const thread_pool_; 700 // Thread local mark stack for this task. 701 const Object* mark_stack_[kMaxSize]; 702 // Mark stack position. 703 size_t mark_stack_pos_; 704 705 void MarkStackPush(const Object* obj) ALWAYS_INLINE { 706 if (UNLIKELY(mark_stack_pos_ == kMaxSize)) { 707 // Mark stack overflow, give 1/2 the stack to the thread pool as a new work task. 708 mark_stack_pos_ /= 2; 709 auto* task = new MarkStackTask(thread_pool_, mark_sweep_, kMaxSize - mark_stack_pos_, 710 mark_stack_ + mark_stack_pos_); 711 thread_pool_->AddTask(Thread::Current(), task); 712 } 713 DCHECK(obj != nullptr); 714 DCHECK(mark_stack_pos_ < kMaxSize); 715 mark_stack_[mark_stack_pos_++] = obj; 716 } 717 718 virtual void Finalize() { 719 delete this; 720 } 721 722 // Scans all of the objects 723 virtual void Run(Thread* self) { 724 ScanObjectParallelVisitor visitor(this); 725 // TODO: Tune this. 726 static const size_t kFifoSize = 4; 727 BoundedFifoPowerOfTwo<const Object*, kFifoSize> prefetch_fifo; 728 for (;;) { 729 const Object* obj = nullptr; 730 if (kUseMarkStackPrefetch) { 731 while (mark_stack_pos_ != 0 && prefetch_fifo.size() < kFifoSize) { 732 const Object* obj = mark_stack_[--mark_stack_pos_]; 733 DCHECK(obj != nullptr); 734 __builtin_prefetch(obj); 735 prefetch_fifo.push_back(obj); 736 } 737 if (UNLIKELY(prefetch_fifo.empty())) { 738 break; 739 } 740 obj = prefetch_fifo.front(); 741 prefetch_fifo.pop_front(); 742 } else { 743 if (UNLIKELY(mark_stack_pos_ == 0)) { 744 break; 745 } 746 obj = mark_stack_[--mark_stack_pos_]; 747 } 748 DCHECK(obj != nullptr); 749 visitor(const_cast<mirror::Object*>(obj)); 750 } 751 } 752}; 753 754class CardScanTask : public MarkStackTask<false> { 755 public: 756 CardScanTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, accounting::SpaceBitmap* bitmap, 757 byte* begin, byte* end, byte minimum_age, size_t mark_stack_size, 758 const Object** mark_stack_obj) 759 : MarkStackTask<false>(thread_pool, mark_sweep, mark_stack_size, mark_stack_obj), 760 bitmap_(bitmap), 761 begin_(begin), 762 end_(end), 763 minimum_age_(minimum_age) { 764 } 765 766 protected: 767 accounting::SpaceBitmap* const bitmap_; 768 byte* const begin_; 769 byte* const end_; 770 const byte minimum_age_; 771 772 virtual void Finalize() { 773 delete this; 774 } 775 776 virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS { 777 ScanObjectParallelVisitor visitor(this); 778 accounting::CardTable* card_table = mark_sweep_->GetHeap()->GetCardTable(); 779 size_t cards_scanned = card_table->Scan(bitmap_, begin_, end_, visitor, minimum_age_); 780 VLOG(heap) << "Parallel scanning cards " << reinterpret_cast<void*>(begin_) << " - " 781 << reinterpret_cast<void*>(end_) << " = " << cards_scanned; 782 // Finish by emptying our local mark stack. 783 MarkStackTask::Run(self); 784 } 785}; 786 787size_t MarkSweep::GetThreadCount(bool paused) const { 788 if (heap_->GetThreadPool() == nullptr || !heap_->CareAboutPauseTimes()) { 789 return 0; 790 } 791 if (paused) { 792 return heap_->GetParallelGCThreadCount() + 1; 793 } else { 794 return heap_->GetConcGCThreadCount() + 1; 795 } 796} 797 798void MarkSweep::ScanGrayObjects(bool paused, byte minimum_age) { 799 accounting::CardTable* card_table = GetHeap()->GetCardTable(); 800 ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 801 size_t thread_count = GetThreadCount(paused); 802 // The parallel version with only one thread is faster for card scanning, TODO: fix. 803 if (kParallelCardScan && thread_count > 0) { 804 Thread* self = Thread::Current(); 805 // Can't have a different split for each space since multiple spaces can have their cards being 806 // scanned at the same time. 807 timings_.StartSplit(paused ? "(Paused)ScanGrayObjects" : "ScanGrayObjects"); 808 // Try to take some of the mark stack since we can pass this off to the worker tasks. 809 const Object** mark_stack_begin = const_cast<const Object**>(mark_stack_->Begin()); 810 const Object** mark_stack_end = const_cast<const Object**>(mark_stack_->End()); 811 const size_t mark_stack_size = mark_stack_end - mark_stack_begin; 812 // Estimated number of work tasks we will create. 813 const size_t mark_stack_tasks = GetHeap()->GetContinuousSpaces().size() * thread_count; 814 DCHECK_NE(mark_stack_tasks, 0U); 815 const size_t mark_stack_delta = std::min(CardScanTask::kMaxSize / 2, 816 mark_stack_size / mark_stack_tasks + 1); 817 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 818 if (space->GetMarkBitmap() == nullptr) { 819 continue; 820 } 821 byte* card_begin = space->Begin(); 822 byte* card_end = space->End(); 823 // Align up the end address. For example, the image space's end 824 // may not be card-size-aligned. 825 card_end = AlignUp(card_end, accounting::CardTable::kCardSize); 826 DCHECK(IsAligned<accounting::CardTable::kCardSize>(card_begin)); 827 DCHECK(IsAligned<accounting::CardTable::kCardSize>(card_end)); 828 // Calculate how many bytes of heap we will scan, 829 const size_t address_range = card_end - card_begin; 830 // Calculate how much address range each task gets. 831 const size_t card_delta = RoundUp(address_range / thread_count + 1, 832 accounting::CardTable::kCardSize); 833 // Create the worker tasks for this space. 834 while (card_begin != card_end) { 835 // Add a range of cards. 836 size_t addr_remaining = card_end - card_begin; 837 size_t card_increment = std::min(card_delta, addr_remaining); 838 // Take from the back of the mark stack. 839 size_t mark_stack_remaining = mark_stack_end - mark_stack_begin; 840 size_t mark_stack_increment = std::min(mark_stack_delta, mark_stack_remaining); 841 mark_stack_end -= mark_stack_increment; 842 mark_stack_->PopBackCount(static_cast<int32_t>(mark_stack_increment)); 843 DCHECK_EQ(mark_stack_end, mark_stack_->End()); 844 // Add the new task to the thread pool. 845 auto* task = new CardScanTask(thread_pool, this, space->GetMarkBitmap(), card_begin, 846 card_begin + card_increment, minimum_age, 847 mark_stack_increment, mark_stack_end); 848 thread_pool->AddTask(self, task); 849 card_begin += card_increment; 850 } 851 } 852 853 // Note: the card scan below may dirty new cards (and scan them) 854 // as a side effect when a Reference object is encountered and 855 // queued during the marking. See b/11465268. 856 thread_pool->SetMaxActiveWorkers(thread_count - 1); 857 thread_pool->StartWorkers(self); 858 thread_pool->Wait(self, true, true); 859 thread_pool->StopWorkers(self); 860 timings_.EndSplit(); 861 } else { 862 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 863 if (space->GetMarkBitmap() != nullptr) { 864 // Image spaces are handled properly since live == marked for them. 865 switch (space->GetGcRetentionPolicy()) { 866 case space::kGcRetentionPolicyNeverCollect: 867 timings_.StartSplit(paused ? "(Paused)ScanGrayImageSpaceObjects" : 868 "ScanGrayImageSpaceObjects"); 869 break; 870 case space::kGcRetentionPolicyFullCollect: 871 timings_.StartSplit(paused ? "(Paused)ScanGrayZygoteSpaceObjects" : 872 "ScanGrayZygoteSpaceObjects"); 873 break; 874 case space::kGcRetentionPolicyAlwaysCollect: 875 timings_.StartSplit(paused ? "(Paused)ScanGrayAllocSpaceObjects" : 876 "ScanGrayAllocSpaceObjects"); 877 break; 878 } 879 ScanObjectVisitor visitor(this); 880 card_table->Scan(space->GetMarkBitmap(), space->Begin(), space->End(), visitor, minimum_age); 881 timings_.EndSplit(); 882 } 883 } 884 } 885} 886 887void MarkSweep::VerifyImageRoots() { 888 // Verify roots ensures that all the references inside the image space point 889 // objects which are either in the image space or marked objects in the alloc 890 // space 891 timings_.StartSplit("VerifyImageRoots"); 892 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 893 if (space->IsImageSpace()) { 894 space::ImageSpace* image_space = space->AsImageSpace(); 895 uintptr_t begin = reinterpret_cast<uintptr_t>(image_space->Begin()); 896 uintptr_t end = reinterpret_cast<uintptr_t>(image_space->End()); 897 accounting::SpaceBitmap* live_bitmap = image_space->GetLiveBitmap(); 898 DCHECK(live_bitmap != NULL); 899 live_bitmap->VisitMarkedRange(begin, end, [this](const Object* obj) { 900 if (kCheckLocks) { 901 Locks::heap_bitmap_lock_->AssertSharedHeld(Thread::Current()); 902 } 903 DCHECK(obj != NULL); 904 CheckObject(obj); 905 }); 906 } 907 } 908 timings_.EndSplit(); 909} 910 911class RecursiveMarkTask : public MarkStackTask<false> { 912 public: 913 RecursiveMarkTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, 914 accounting::SpaceBitmap* bitmap, uintptr_t begin, uintptr_t end) 915 : MarkStackTask<false>(thread_pool, mark_sweep, 0, NULL), 916 bitmap_(bitmap), 917 begin_(begin), 918 end_(end) { 919 } 920 921 protected: 922 accounting::SpaceBitmap* const bitmap_; 923 const uintptr_t begin_; 924 const uintptr_t end_; 925 926 virtual void Finalize() { 927 delete this; 928 } 929 930 // Scans all of the objects 931 virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS { 932 ScanObjectParallelVisitor visitor(this); 933 bitmap_->VisitMarkedRange(begin_, end_, visitor); 934 // Finish by emptying our local mark stack. 935 MarkStackTask::Run(self); 936 } 937}; 938 939// Populates the mark stack based on the set of marked objects and 940// recursively marks until the mark stack is emptied. 941void MarkSweep::RecursiveMark() { 942 TimingLogger::ScopedSplit split("RecursiveMark", &timings_); 943 // RecursiveMark will build the lists of known instances of the Reference classes. 944 // See DelayReferenceReferent for details. 945 CHECK(soft_reference_list_ == NULL); 946 CHECK(weak_reference_list_ == NULL); 947 CHECK(finalizer_reference_list_ == NULL); 948 CHECK(phantom_reference_list_ == NULL); 949 CHECK(cleared_reference_list_ == NULL); 950 951 if (kUseRecursiveMark) { 952 const bool partial = GetGcType() == kGcTypePartial; 953 ScanObjectVisitor scan_visitor(this); 954 auto* self = Thread::Current(); 955 ThreadPool* thread_pool = heap_->GetThreadPool(); 956 size_t thread_count = GetThreadCount(false); 957 const bool parallel = kParallelRecursiveMark && thread_count > 1; 958 mark_stack_->Reset(); 959 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 960 if ((space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) || 961 (!partial && space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect)) { 962 current_mark_bitmap_ = space->GetMarkBitmap(); 963 if (current_mark_bitmap_ == nullptr) { 964 continue; 965 } 966 if (parallel) { 967 // We will use the mark stack the future. 968 // CHECK(mark_stack_->IsEmpty()); 969 // This function does not handle heap end increasing, so we must use the space end. 970 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 971 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 972 atomic_finger_ = static_cast<int32_t>(0xFFFFFFFF); 973 974 // Create a few worker tasks. 975 const size_t n = thread_count * 2; 976 while (begin != end) { 977 uintptr_t start = begin; 978 uintptr_t delta = (end - begin) / n; 979 delta = RoundUp(delta, KB); 980 if (delta < 16 * KB) delta = end - begin; 981 begin += delta; 982 auto* task = new RecursiveMarkTask(thread_pool, this, current_mark_bitmap_, start, 983 begin); 984 thread_pool->AddTask(self, task); 985 } 986 thread_pool->SetMaxActiveWorkers(thread_count - 1); 987 thread_pool->StartWorkers(self); 988 thread_pool->Wait(self, true, true); 989 thread_pool->StopWorkers(self); 990 } else { 991 // This function does not handle heap end increasing, so we must use the space end. 992 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 993 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 994 current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor); 995 } 996 } 997 } 998 } 999 ProcessMarkStack(false); 1000} 1001 1002mirror::Object* MarkSweep::IsMarkedCallback(Object* object, void* arg) { 1003 if (reinterpret_cast<MarkSweep*>(arg)->IsMarked(object)) { 1004 return object; 1005 } 1006 return nullptr; 1007} 1008 1009void MarkSweep::RecursiveMarkDirtyObjects(bool paused, byte minimum_age) { 1010 ScanGrayObjects(paused, minimum_age); 1011 ProcessMarkStack(paused); 1012} 1013 1014void MarkSweep::ReMarkRoots() { 1015 timings_.StartSplit("ReMarkRoots"); 1016 Runtime::Current()->VisitRoots(MarkRootCallback, this, true, true); 1017 timings_.EndSplit(); 1018} 1019 1020void MarkSweep::SweepSystemWeaks() { 1021 Runtime* runtime = Runtime::Current(); 1022 timings_.StartSplit("SweepSystemWeaks"); 1023 runtime->SweepSystemWeaks(IsMarkedCallback, this); 1024 timings_.EndSplit(); 1025} 1026 1027mirror::Object* MarkSweep::VerifySystemWeakIsLiveCallback(Object* obj, void* arg) { 1028 reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj); 1029 // We don't actually want to sweep the object, so lets return "marked" 1030 return obj; 1031} 1032 1033void MarkSweep::VerifyIsLive(const Object* obj) { 1034 Heap* heap = GetHeap(); 1035 if (!heap->GetLiveBitmap()->Test(obj)) { 1036 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 1037 if (!large_object_space->GetLiveObjects()->Test(obj)) { 1038 if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) == 1039 heap->allocation_stack_->End()) { 1040 // Object not found! 1041 heap->DumpSpaces(); 1042 LOG(FATAL) << "Found dead object " << obj; 1043 } 1044 } 1045 } 1046} 1047 1048void MarkSweep::VerifySystemWeaks() { 1049 // Verify system weaks, uses a special object visitor which returns the input object. 1050 Runtime::Current()->SweepSystemWeaks(VerifySystemWeakIsLiveCallback, this); 1051} 1052 1053struct SweepCallbackContext { 1054 MarkSweep* mark_sweep; 1055 space::AllocSpace* space; 1056 Thread* self; 1057}; 1058 1059class CheckpointMarkThreadRoots : public Closure { 1060 public: 1061 explicit CheckpointMarkThreadRoots(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {} 1062 1063 virtual void Run(Thread* thread) NO_THREAD_SAFETY_ANALYSIS { 1064 ATRACE_BEGIN("Marking thread roots"); 1065 // Note: self is not necessarily equal to thread since thread may be suspended. 1066 Thread* self = Thread::Current(); 1067 CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 1068 << thread->GetState() << " thread " << thread << " self " << self; 1069 thread->VisitRoots(MarkSweep::MarkRootParallelCallback, mark_sweep_); 1070 ATRACE_END(); 1071 mark_sweep_->GetBarrier().Pass(self); 1072 } 1073 1074 private: 1075 MarkSweep* mark_sweep_; 1076}; 1077 1078void MarkSweep::MarkRootsCheckpoint(Thread* self) { 1079 CheckpointMarkThreadRoots check_point(this); 1080 timings_.StartSplit("MarkRootsCheckpoint"); 1081 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 1082 // Request the check point is run on all threads returning a count of the threads that must 1083 // run through the barrier including self. 1084 size_t barrier_count = thread_list->RunCheckpoint(&check_point); 1085 // Release locks then wait for all mutator threads to pass the barrier. 1086 // TODO: optimize to not release locks when there are no threads to wait for. 1087 Locks::heap_bitmap_lock_->ExclusiveUnlock(self); 1088 Locks::mutator_lock_->SharedUnlock(self); 1089 ThreadState old_state = self->SetState(kWaitingForCheckPointsToRun); 1090 CHECK_EQ(old_state, kWaitingPerformingGc); 1091 gc_barrier_->Increment(self, barrier_count); 1092 self->SetState(kWaitingPerformingGc); 1093 Locks::mutator_lock_->SharedLock(self); 1094 Locks::heap_bitmap_lock_->ExclusiveLock(self); 1095 timings_.EndSplit(); 1096} 1097 1098void MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 1099 SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 1100 MarkSweep* mark_sweep = context->mark_sweep; 1101 Heap* heap = mark_sweep->GetHeap(); 1102 space::AllocSpace* space = context->space; 1103 Thread* self = context->self; 1104 Locks::heap_bitmap_lock_->AssertExclusiveHeld(self); 1105 // Use a bulk free, that merges consecutive objects before freeing or free per object? 1106 // Documentation suggests better free performance with merging, but this may be at the expensive 1107 // of allocation. 1108 size_t freed_objects = num_ptrs; 1109 // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit 1110 size_t freed_bytes = space->FreeList(self, num_ptrs, ptrs); 1111 heap->RecordFree(freed_objects, freed_bytes); 1112 mark_sweep->freed_objects_.fetch_add(freed_objects); 1113 mark_sweep->freed_bytes_.fetch_add(freed_bytes); 1114} 1115 1116void MarkSweep::ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg) { 1117 SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg); 1118 Locks::heap_bitmap_lock_->AssertExclusiveHeld(context->self); 1119 Heap* heap = context->mark_sweep->GetHeap(); 1120 // We don't free any actual memory to avoid dirtying the shared zygote pages. 1121 for (size_t i = 0; i < num_ptrs; ++i) { 1122 Object* obj = static_cast<Object*>(ptrs[i]); 1123 heap->GetLiveBitmap()->Clear(obj); 1124 heap->GetCardTable()->MarkCard(obj); 1125 } 1126} 1127 1128void MarkSweep::SweepArray(accounting::ObjectStack* allocations, bool swap_bitmaps) { 1129 space::MallocSpace* space = heap_->GetNonMovingSpace(); 1130 timings_.StartSplit("SweepArray"); 1131 // Newly allocated objects MUST be in the alloc space and those are the only objects which we are 1132 // going to free. 1133 accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 1134 accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 1135 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 1136 accounting::SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 1137 accounting::SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 1138 if (swap_bitmaps) { 1139 std::swap(live_bitmap, mark_bitmap); 1140 std::swap(large_live_objects, large_mark_objects); 1141 } 1142 1143 size_t freed_bytes = 0; 1144 size_t freed_large_object_bytes = 0; 1145 size_t freed_objects = 0; 1146 size_t freed_large_objects = 0; 1147 size_t count = allocations->Size(); 1148 Object** objects = const_cast<Object**>(allocations->Begin()); 1149 Object** out = objects; 1150 Object** objects_to_chunk_free = out; 1151 1152 // Empty the allocation stack. 1153 Thread* self = Thread::Current(); 1154 for (size_t i = 0; i < count; ++i) { 1155 Object* obj = objects[i]; 1156 // There should only be objects in the AllocSpace/LargeObjectSpace in the allocation stack. 1157 if (LIKELY(mark_bitmap->HasAddress(obj))) { 1158 if (!mark_bitmap->Test(obj)) { 1159 // Don't bother un-marking since we clear the mark bitmap anyways. 1160 *(out++) = obj; 1161 // Free objects in chunks. 1162 DCHECK_GE(out, objects_to_chunk_free); 1163 DCHECK_LE(static_cast<size_t>(out - objects_to_chunk_free), kSweepArrayChunkFreeSize); 1164 if (static_cast<size_t>(out - objects_to_chunk_free) == kSweepArrayChunkFreeSize) { 1165 timings_.StartSplit("FreeList"); 1166 size_t chunk_freed_objects = out - objects_to_chunk_free; 1167 freed_objects += chunk_freed_objects; 1168 freed_bytes += space->FreeList(self, chunk_freed_objects, objects_to_chunk_free); 1169 objects_to_chunk_free = out; 1170 timings_.EndSplit(); 1171 } 1172 } 1173 } else if (!large_mark_objects->Test(obj)) { 1174 ++freed_large_objects; 1175 freed_large_object_bytes += large_object_space->Free(self, obj); 1176 } 1177 } 1178 // Free the remaining objects in chunks. 1179 DCHECK_GE(out, objects_to_chunk_free); 1180 DCHECK_LE(static_cast<size_t>(out - objects_to_chunk_free), kSweepArrayChunkFreeSize); 1181 if (out - objects_to_chunk_free > 0) { 1182 timings_.StartSplit("FreeList"); 1183 size_t chunk_freed_objects = out - objects_to_chunk_free; 1184 freed_objects += chunk_freed_objects; 1185 freed_bytes += space->FreeList(self, chunk_freed_objects, objects_to_chunk_free); 1186 timings_.EndSplit(); 1187 } 1188 CHECK_EQ(count, allocations->Size()); 1189 timings_.EndSplit(); 1190 1191 timings_.StartSplit("RecordFree"); 1192 VLOG(heap) << "Freed " << freed_objects << "/" << count 1193 << " objects with size " << PrettySize(freed_bytes); 1194 heap_->RecordFree(freed_objects + freed_large_objects, freed_bytes + freed_large_object_bytes); 1195 freed_objects_.fetch_add(freed_objects); 1196 freed_large_objects_.fetch_add(freed_large_objects); 1197 freed_bytes_.fetch_add(freed_bytes); 1198 freed_large_object_bytes_.fetch_add(freed_large_object_bytes); 1199 timings_.EndSplit(); 1200 1201 timings_.StartSplit("ResetStack"); 1202 allocations->Reset(); 1203 timings_.EndSplit(); 1204} 1205 1206void MarkSweep::Sweep(bool swap_bitmaps) { 1207 DCHECK(mark_stack_->IsEmpty()); 1208 TimingLogger::ScopedSplit("Sweep", &timings_); 1209 1210 const bool partial = (GetGcType() == kGcTypePartial); 1211 SweepCallbackContext scc; 1212 scc.mark_sweep = this; 1213 scc.self = Thread::Current(); 1214 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1215 if (!space->IsMallocSpace()) { 1216 continue; 1217 } 1218 // We always sweep always collect spaces. 1219 bool sweep_space = space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect; 1220 if (!partial && !sweep_space) { 1221 // We sweep full collect spaces when the GC isn't a partial GC (ie its full). 1222 sweep_space = (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect); 1223 } 1224 if (sweep_space) { 1225 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 1226 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 1227 scc.space = space->AsMallocSpace(); 1228 accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 1229 accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 1230 if (swap_bitmaps) { 1231 std::swap(live_bitmap, mark_bitmap); 1232 } 1233 if (!space->IsZygoteSpace()) { 1234 TimingLogger::ScopedSplit split("SweepAllocSpace", &timings_); 1235 // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked. 1236 accounting::SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 1237 &SweepCallback, reinterpret_cast<void*>(&scc)); 1238 } else { 1239 TimingLogger::ScopedSplit split("SweepZygote", &timings_); 1240 // Zygote sweep takes care of dirtying cards and clearing live bits, does not free actual 1241 // memory. 1242 accounting::SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end, 1243 &ZygoteSweepCallback, reinterpret_cast<void*>(&scc)); 1244 } 1245 } 1246 } 1247 1248 SweepLargeObjects(swap_bitmaps); 1249} 1250 1251void MarkSweep::SweepLargeObjects(bool swap_bitmaps) { 1252 TimingLogger::ScopedSplit("SweepLargeObjects", &timings_); 1253 // Sweep large objects 1254 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 1255 accounting::SpaceSetMap* large_live_objects = large_object_space->GetLiveObjects(); 1256 accounting::SpaceSetMap* large_mark_objects = large_object_space->GetMarkObjects(); 1257 if (swap_bitmaps) { 1258 std::swap(large_live_objects, large_mark_objects); 1259 } 1260 // O(n*log(n)) but hopefully there are not too many large objects. 1261 size_t freed_objects = 0; 1262 size_t freed_bytes = 0; 1263 Thread* self = Thread::Current(); 1264 for (const Object* obj : large_live_objects->GetObjects()) { 1265 if (!large_mark_objects->Test(obj)) { 1266 freed_bytes += large_object_space->Free(self, const_cast<Object*>(obj)); 1267 ++freed_objects; 1268 } 1269 } 1270 freed_large_objects_.fetch_add(freed_objects); 1271 freed_large_object_bytes_.fetch_add(freed_bytes); 1272 GetHeap()->RecordFree(freed_objects, freed_bytes); 1273} 1274 1275void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) { 1276 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1277 if (space->IsMallocSpace() && space->Contains(ref)) { 1278 DCHECK(IsMarked(obj)); 1279 1280 bool is_marked = IsMarked(ref); 1281 if (!is_marked) { 1282 LOG(INFO) << *space; 1283 LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref) 1284 << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj) 1285 << "' (" << reinterpret_cast<const void*>(obj) << ") at offset " 1286 << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked"; 1287 1288 const Class* klass = is_static ? obj->AsClass() : obj->GetClass(); 1289 DCHECK(klass != NULL); 1290 const ObjectArray<ArtField>* fields = is_static ? klass->GetSFields() : klass->GetIFields(); 1291 DCHECK(fields != NULL); 1292 bool found = false; 1293 for (int32_t i = 0; i < fields->GetLength(); ++i) { 1294 const ArtField* cur = fields->Get(i); 1295 if (cur->GetOffset().Int32Value() == offset.Int32Value()) { 1296 LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur); 1297 found = true; 1298 break; 1299 } 1300 } 1301 if (!found) { 1302 LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value(); 1303 } 1304 1305 bool obj_marked = heap_->GetCardTable()->IsDirty(obj); 1306 if (!obj_marked) { 1307 LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' " 1308 << "(" << reinterpret_cast<const void*>(obj) << ") contains references to " 1309 << "the alloc space, but wasn't card marked"; 1310 } 1311 } 1312 } 1313 break; 1314 } 1315} 1316 1317// Process the "referent" field in a java.lang.ref.Reference. If the 1318// referent has not yet been marked, put it on the appropriate list in 1319// the heap for later processing. 1320void MarkSweep::DelayReferenceReferent(mirror::Class* klass, Object* obj) { 1321 DCHECK(klass != nullptr); 1322 DCHECK(klass->IsReferenceClass()); 1323 DCHECK(obj != NULL); 1324 heap_->DelayReferenceReferent(klass, obj, IsMarkedCallback, this); 1325} 1326 1327class MarkObjectVisitor { 1328 public: 1329 explicit MarkObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE : mark_sweep_(mark_sweep) {} 1330 1331 // TODO: Fixme when anotatalysis works with visitors. 1332 void operator()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, 1333 bool /* is_static */) const ALWAYS_INLINE 1334 NO_THREAD_SAFETY_ANALYSIS { 1335 if (kCheckLocks) { 1336 Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 1337 Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 1338 } 1339 mark_sweep_->MarkObject(ref); 1340 } 1341 1342 private: 1343 MarkSweep* const mark_sweep_; 1344}; 1345 1346// Scans an object reference. Determines the type of the reference 1347// and dispatches to a specialized scanning routine. 1348void MarkSweep::ScanObject(Object* obj) { 1349 MarkObjectVisitor visitor(this); 1350 ScanObjectVisit(obj, visitor); 1351} 1352 1353void MarkSweep::ProcessMarkStackParallel(size_t thread_count) { 1354 Thread* self = Thread::Current(); 1355 ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 1356 const size_t chunk_size = std::min(mark_stack_->Size() / thread_count + 1, 1357 static_cast<size_t>(MarkStackTask<false>::kMaxSize)); 1358 CHECK_GT(chunk_size, 0U); 1359 // Split the current mark stack up into work tasks. 1360 for (mirror::Object **it = mark_stack_->Begin(), **end = mark_stack_->End(); it < end; ) { 1361 const size_t delta = std::min(static_cast<size_t>(end - it), chunk_size); 1362 thread_pool->AddTask(self, new MarkStackTask<false>(thread_pool, this, delta, 1363 const_cast<const mirror::Object**>(it))); 1364 it += delta; 1365 } 1366 thread_pool->SetMaxActiveWorkers(thread_count - 1); 1367 thread_pool->StartWorkers(self); 1368 thread_pool->Wait(self, true, true); 1369 thread_pool->StopWorkers(self); 1370 mark_stack_->Reset(); 1371 CHECK_EQ(work_chunks_created_, work_chunks_deleted_) << " some of the work chunks were leaked"; 1372} 1373 1374// Scan anything that's on the mark stack. 1375void MarkSweep::ProcessMarkStack(bool paused) { 1376 timings_.StartSplit("ProcessMarkStack"); 1377 size_t thread_count = GetThreadCount(paused); 1378 if (kParallelProcessMarkStack && thread_count > 1 && 1379 mark_stack_->Size() >= kMinimumParallelMarkStackSize) { 1380 ProcessMarkStackParallel(thread_count); 1381 } else { 1382 // TODO: Tune this. 1383 static const size_t kFifoSize = 4; 1384 BoundedFifoPowerOfTwo<Object*, kFifoSize> prefetch_fifo; 1385 for (;;) { 1386 Object* obj = NULL; 1387 if (kUseMarkStackPrefetch) { 1388 while (!mark_stack_->IsEmpty() && prefetch_fifo.size() < kFifoSize) { 1389 Object* obj = mark_stack_->PopBack(); 1390 DCHECK(obj != NULL); 1391 __builtin_prefetch(obj); 1392 prefetch_fifo.push_back(obj); 1393 } 1394 if (prefetch_fifo.empty()) { 1395 break; 1396 } 1397 obj = prefetch_fifo.front(); 1398 prefetch_fifo.pop_front(); 1399 } else { 1400 if (mark_stack_->IsEmpty()) { 1401 break; 1402 } 1403 obj = mark_stack_->PopBack(); 1404 } 1405 DCHECK(obj != NULL); 1406 ScanObject(obj); 1407 } 1408 } 1409 timings_.EndSplit(); 1410} 1411 1412inline bool MarkSweep::IsMarked(const Object* object) const 1413 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 1414 if (IsImmune(object)) { 1415 return true; 1416 } 1417 DCHECK(current_mark_bitmap_ != NULL); 1418 if (current_mark_bitmap_->HasAddress(object)) { 1419 return current_mark_bitmap_->Test(object); 1420 } 1421 return heap_->GetMarkBitmap()->Test(object); 1422} 1423 1424void MarkSweep::UnBindBitmaps() { 1425 TimingLogger::ScopedSplit split("UnBindBitmaps", &timings_); 1426 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1427 if (space->IsMallocSpace()) { 1428 space::MallocSpace* alloc_space = space->AsMallocSpace(); 1429 if (alloc_space->temp_bitmap_.get() != NULL) { 1430 // At this point, the temp_bitmap holds our old mark bitmap. 1431 accounting::SpaceBitmap* new_bitmap = alloc_space->temp_bitmap_.release(); 1432 GetHeap()->GetMarkBitmap()->ReplaceBitmap(alloc_space->mark_bitmap_.get(), new_bitmap); 1433 CHECK_EQ(alloc_space->mark_bitmap_.release(), alloc_space->live_bitmap_.get()); 1434 alloc_space->mark_bitmap_.reset(new_bitmap); 1435 DCHECK(alloc_space->temp_bitmap_.get() == NULL); 1436 } 1437 } 1438 } 1439} 1440 1441void MarkSweep::FinishPhase() { 1442 TimingLogger::ScopedSplit split("FinishPhase", &timings_); 1443 // Can't enqueue references if we hold the mutator lock. 1444 Heap* heap = GetHeap(); 1445 timings_.NewSplit("PostGcVerification"); 1446 heap->PostGcVerification(this); 1447 1448 timings_.NewSplit("RequestHeapTrim"); 1449 heap->RequestHeapTrim(); 1450 1451 // Update the cumulative statistics 1452 total_time_ns_ += GetDurationNs(); 1453 total_paused_time_ns_ += std::accumulate(GetPauseTimes().begin(), GetPauseTimes().end(), 0, 1454 std::plus<uint64_t>()); 1455 total_freed_objects_ += GetFreedObjects() + GetFreedLargeObjects(); 1456 total_freed_bytes_ += GetFreedBytes() + GetFreedLargeObjectBytes(); 1457 1458 // Ensure that the mark stack is empty. 1459 CHECK(mark_stack_->IsEmpty()); 1460 1461 if (kCountScannedTypes) { 1462 VLOG(gc) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ 1463 << " other=" << other_count_; 1464 } 1465 1466 if (kCountTasks) { 1467 VLOG(gc) << "Total number of work chunks allocated: " << work_chunks_created_; 1468 } 1469 1470 if (kMeasureOverhead) { 1471 VLOG(gc) << "Overhead time " << PrettyDuration(overhead_time_); 1472 } 1473 1474 if (kProfileLargeObjects) { 1475 VLOG(gc) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_; 1476 } 1477 1478 if (kCountClassesMarked) { 1479 VLOG(gc) << "Classes marked " << classes_marked_; 1480 } 1481 1482 if (kCountJavaLangRefs) { 1483 VLOG(gc) << "References scanned " << reference_count_; 1484 } 1485 1486 // Update the cumulative loggers. 1487 cumulative_timings_.Start(); 1488 cumulative_timings_.AddLogger(timings_); 1489 cumulative_timings_.End(); 1490 1491 // Clear all of the spaces' mark bitmaps. 1492 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1493 accounting::SpaceBitmap* bitmap = space->GetMarkBitmap(); 1494 if (bitmap != nullptr && 1495 space->GetGcRetentionPolicy() != space::kGcRetentionPolicyNeverCollect) { 1496 bitmap->Clear(); 1497 } 1498 } 1499 mark_stack_->Reset(); 1500 1501 // Reset the marked large objects. 1502 space::LargeObjectSpace* large_objects = GetHeap()->GetLargeObjectsSpace(); 1503 large_objects->GetMarkObjects()->Clear(); 1504} 1505 1506} // namespace collector 1507} // namespace gc 1508} // namespace art 1509