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